An infinite stream of numbers is given. The stream is stopped at an arbitrary point. Return any number of the stream read till now with equal probability, using O(1) space.
p.s. Question asked in telephonic round of Tower Research Capital for High Frequency Trading Profile
can you pls explain what do you mean by “equal probablity” …
I believe he means to say that, if we read K numbers, we should choose anyone of them with probability 1/K, to be equally likely to get each one of the K numbers.
THis would be trivial to do if we could keep on storing the numbers read in a list or so, then we use a uniform probability distribution generator to generate a number between 1 and K, let it be S, and we return the number at the index Array[S-1].
The main difficulty here is the space requirement to be O(1)… while we could always return the last number read, that would violate the condition of equal probability…
Bruno
I guess you can solve it with the unique properties of number pi. In the decimal expansion of pi all digits occur with equal probability. As the question states there is infinite stream of number you can assume infinite numbers were inputted before the stream stopped. Now all you need to do is generate a starting point for that use any uniform probability distribution generator and repeat for the ending point. After that print all the digits in the decimal expansion of pi from start to end. By doing so you will be generating a random number with equal probability.
Do point out if this seems wrong/absurd.