CareerCup

Take the first number off the stream, use its absolute value as an index in the stream. If the numbers themselves are infinite, this should answer it.

assume you have a memory space B stores the number you pick
1. starting from the very first from the stream A, assign B = A_1
2. move to the next one, if rand() > 1/2, assign B = A_2
3. move to the next one, if rand() > 2/3 assign B = A_3
...
k. move to the next one, if rand() > (k-1)/k assign B = A_k
...

you are guaranteed to give equal probability to each element

colin is right. The algorithm he used has a name: Reservoir Sampling.

To CyberPhoenix, foobar, wiwi: Huh?

interesting question - i think that's the problem here is that the count in infinite.
If you assume that rand() returns a number from the infinite range 0 - 1 we an simply use that - the decimal part can be construed as index into this stream.

But theres something wrong with the above solution and I don't yet know how to improve it.
Well, rand() is a computer based function, and computers work with finite numbers (i.e. floating point is not infinite math).

A rand function cannot have an infinite range. When we see a number in the infinite stream, we basically can pick it or not pick it. How can we design an algorithm that the probability that a number is picked is the same for all numbers?

I had a similar question in Cisco interview.

The question was more or less the same.

The interviewer was satisfied with rand()

1.Generate a Gaussian Distribution float number x, between 0 and 1
2.1/x will be the random number for a infinite series.

can you point us to some more info on how x, which is from a finite set, becomes a pick from infinite series, when you take its reciprocal ?

I had similar question asked in one of interviews. If you got for rand(), the probability won't be equal for all numbers.

Answer is simple....
It is a continuous stream, just keep track of the size of the data received.
Suppose currently you have 10 bytes, with this information you can easily pick number with equal probability. Assuming rand(10) picks number with equal probability rand(current_size) will do the trick.
int total= 0,size = 0;
while(true)
size = read(socket,buff,sizeof(buff));
total +=size;
}
rand(total); will give the number ....

Do we know the total number (count) of the numbers?