Uniform selection from unknown range
June 30th, 2012 § 6 Comments
I have heard the following puzzle from a colleague I work with. It should be fairly simple, but is still pretty interesting to solve. The solution technique might come in handy for solving various other puzzles, and even for real-world problems. But enough with the introduction, let us cut to the chase.
You are given a black box that is able to generate numbers. You know nothing about the range of these numbers.
At some point, this black box will be done generating the numbers and will not be able to produce any more of them. You obviously can not know in advance how many numbers are going to be generated.
Once all numbers have been generated, the black box can no longer be used. It can not re-generate the same sequence nor does it have any other use.
You are allowed to count the generated elements, and only store a few of them (you may use sufficient memory to store a constant, O(1), number of elements).
Your mission, should you choose to accept it, is to propose an algorithm which will be able to make a uniform selection in the given scenario. That is, you will have to provide an algorithm which satisfies the requirement that every generated element has the same chance to get picked as the output of the algorithm.