This is an interview question I've had.

Your number space is between 0 to N. You can only draw M random samples from 0 to N (N >= M). How many times (T) would you need to draw from your number space to make sure you have X% of the numbers of N. Prove mathematically and programmatically. Note: sampling = TRUE.

For example, to give numeric examples to these, the numbers that you can potentially draw from is between 0 and let's say 400,000,000 (N). You can only draw 50,000,000 (M). Each time you draw, the draw is done randomly between 0 to 400 Million (with replacement), meaning that all 50 Million draws could be 1 (however unlikely). Your objective is to do the minimum number of draws until you've gotten 95% (X%) of the 400 Million (N) numbers. How many times would you need to draw M samples (T) to feel that you have gotten 95% (X) of the numbers of N or 95% of the complete set of N, so about 350,000,000 number? Please note, for clarification, if you draw the number 2 in first round and draw the number 2 in the second round, that doesn't improve your odds cause you already collected the number two in the first round. You want to complete as much of the set as possible.

Show mathematically and programmatically.


My thoughts on the question and my answer.This is a binomial question with probability 350M/400M = 12.5%. A quick way: is plotting 1:100 and then doing plotting y axis (1 - Probability)^(1:100)) and seeing at what number it hits 0.05.

Mathematically, I forgot how to prove it, lol. Can someone tell me their thoughts and answer, for both programmatically and mathematically?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.