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.

>>12
I'm probabilitying as fast as I can, home-slice. Only because they overwrite do the values have an equal value of being selected. You don't return until the end of the scan; until then you just hold the variable in memory. I think you understand that.

Consider the straight-forward case: we know we have 3 elements and we want to know what probability each should be considered with in order to produce 1/3 chance of selection:

Item 1: 1/3
Item 2: 1/2
Item 3: 1

The solution I gave in >>10 works by reversing this. ... or maybe it doesn't. I'm not sure.

If it isn't, it's impossible to solve this problem without storing all of the variables in some fashion.