Programming Interview Questions

You have a stream of numbers that you can see one at a time. With uniform probability, select only one of these numbers. That is, each number in the stream has the same probability of being selected. You cannot just store the entire stream to an array or read through the stream twice.

>>4
Seriously bro? That's just a variation on storing the stream in an array. All you're doing is throwing MapReduce at the same unacceptable strategy—you're still finding a way to look at an input element more than once.

Aha! Wait, I think I may have a plan.

Start by selecting the first number. Then, with probability 1/i, overwrite it with the next item in the stream. This works perfectly.