Re: some interview questions


Denis Feldmann wrote:
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


True, or you can generate an approximation from scratch.
However, rough order of magnitude is all that is needed here.

-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: Visualization of unmeasurable sets and computability
    ... it does not have to be exact! ... No visualizations are ... rough approximation of the postivie-measure Cantor set: ... draw a rough, ...
    (sci.math)
  • Re: Linux Counter: 128655 registered Linux users
    ... Calling it even a *rough* approximation is a gross exaggeration. ... has no connection at all with the actual number of Linux users. ...
    (comp.os.linux.misc)
  • 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)