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.

Solution: 记录count和sample，当新进一个元素时，count++，求random.nextInt(count)，如果等于0，则更新sample为该元素

  private int count;
  private Integer sample;
  public Solution() {
    count = 0;
    sample = null;
  }

  public void read(int value) {
    count++;
    int r = (int)(Math.random() * count);
    if (r == 0) {
      sample = value;
    }
  }

  public Integer sample() {
    return sample;
  }