Re: some interview questions

William Hughes a écrit :
David R Tribble wrote:

How come no one has attempted an answer to (2)?

Because it is rather harder :)

Recall the question is;

2. Suppose you have a function that returns random 64-bit integers
without checking if a particular integer has already been used. How
many integers would be returned before the probability that an
integer
has been repeated is above 0.5?

This is, of course, the birthday problem. But with the very large
2^64,
computation of the exact answer is not practical,





so an approximation
is
needed.

A very rough approximation can be made by saying that if I choose N
numbers
I get N(N-1)/2 pairs. Since each pair has a 1/2^64 chance of matching,
I need about 2^63 pairs to get a probability of 1/2 (I did say very
rough),
so I need N(N-1) = 2^64, so N is about 2^32.
More careful analysis shows that this is only off by about 20%.
However, even the rough solution indicates
the important fact that given X uniformly distributed outcomes,
one needs about sqrt(x) tries to get a repeat, and the interviewer.
would probably be satisifed.


In fact, you are looking for n such that P= prod (N-k)/N (k=0..n-1) =0.5, with N=2^64. P=N^-n N!/(N-n)!, and Stirling formula will give a very good approximation of that

-William Hughes

.

Relevant Pages

  • Re: some interview questions
    ... A very rough approximation can be made by saying that if I choose N ... I need about 2^63 pairs to get a probability of 1/2 (I did say very ... one needs about sqrttries to get a repeat, ...
    (sci.math)
  • Re: some interview questions
    ... A very rough approximation can be made by saying that if I choose N ... I need about 2^63 pairs to get a probability of 1/2 (I did say very ... one needs about sqrttries to get a repeat, ...
    (sci.math)
  • Re: math problem from an interview
    ... many integers would be returned before the probability that an integer ... repeat be above 0.5. ... For 1 bit, if you fetch two numbers, the probability of a clash is 0.5. ... approximation appears to hold good as the numbers get bigger. ...
    (comp.programming)
  • Re: A Gambling Math Question
    ... Let p be the probability of success and q = 1-p = probability of failure. ... The standard deviation is approximately sqrt. ... But the approximation comes in replacing the binomial ... distribution with a normal distribution having the same mean and standard ...
    (sci.math)
  • Re: Primes, probability and politics
    ... You also ignored me last week when I pointed out the footnote in Hardy ... Considerations of this kind explain why the usual "probability" ... Hardy & Wright: ... excellent approximation to your guess, while both of those suck as ...
    (sci.math)