Consider an unlimited flow of data elements. How do you sample one element from this flow, such that at any point during the processing of the flow, you can return a random element from the n elements read so far.

You will implement two methods for a sampling class:

read(int value) - read one number from the flow

sample() - return at any time the sample, if n values have been read, the probability of returning any one of the n values is 1/n, return null(Java)/INT_MIN(C++) if there is no value read so far

You may need to add more fields for the class.

Assumption: we have a random generator to get a random number.

Approach: keep a count to record how many elements we have read. then get a random number from 0 - count. if the number == 0 , keep the sample. then keep the original one.