Jane Street interview question
Select a random element from a stream with uniform probability (we only have access to the current element, and a function to get the next element which returns EOF when at the end of the stream).
Interview Answers
Anonymous
12 Jun 2015
Reservoir sampling. Pick and save the first current element, (i=1) and for the ith current element afterward, discard saved and replace with current element with probability 1/i. The element you will have at the end of the stream will be a random element with uniform probability. For example, given stream 8 9 11 pick 8 first, S = 8 replace 8 by 9 with probability 1/2, S = x replace x with 11 with probability 1/3, Proof that it works is by induction.
5