CareerCup

it's classic reservoir sampling problem, say space limit is N,
first fill sentences into the space until full, then start from N+1 element in stream, get random number between 1 and N+1, and if the number is smaller than N,
then put this one into space, and we also have to randomly remove one that is already in space by get a random number between 1 and N, then keep doing this till stream exhausted.

1st iteration-
temp = read 1st sentence;
i=2;

while((sentence =  read i-th sentence from stream) != null) { //keep reading till stream is exhausted
     if random() > i/(i+1){
          temp = sentence;
     }
}

return temp;

Good question

what is random() returning here....decimal or whole number?
If whole number how would this logic work?
for instance if random() is returning 7 and if we have 10 lines in stream we expect the logic to return 7th line from the stream.
This logic would return 10th line, becos for every iteration always random() > i / (i+1)is true. ( 7 > 2/3 , 7 > 3/4, 7 > 4/5 and so on...)

Hi,
Can you please also mention the amazon location where this question was asked?

we see each sentence in the stream one after the other, as in we first see the 1st then the 2nd .....the i'th and so on.

to get a random sentence, accept the current sentence as sample with probability (1/i)...this will give us a random sentence with constant space requirement.