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

Assumptions

• k > = 1

You will implement two methods for a sampling class:

• read(int value) - read one number from the flow
• sample() - return at any time the k samples as a list, return the list of all values read when the number of values read so fas < = k.

You may need to add more fields for the class.

Solution: 记录count和list of samples，当新进一个元素时，count++，如果count <= k，直接加进list，否则求random.nextInt(count)，如果index < k，则更新list中第index个元素为该元素

  private final int k;
  private List<Integer> samples;
  private int count;

  public Solution(int k) {
    this.k = k;
    count = 0;
    samples = new ArrayList<Integer>();
  }

  public void read(int value) {
    count++;
    if (count <= k) {
      samples.add(value);
    } else {
      int r = (int)(Math.random() * count);
      if (r < k) {
        samples.set(r, value);
      }
    }
  }

  public List<Integer> sample() {
    return samples;
  }