Reservoir Sampling

Problem: Randomly choosing k samples from a list of n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn’t fit into main memory.

Algorithm:

1. Create an array reservoir[0..k-1] and copy first k items of stream[] to it;

2. Now one by one consider all items from (k+1)th item to nth item:

   (1) Generate a random number from 0 to i where i is index of current item in stream[].

    Assume the random number is j;
   

   (2) If j is in range [0, k-1], replace reservoir[j] with stream[i];

Linked List Random Node

Analysis:

1.Keep a reservoir containing only one element;
2.Use index i to keep track of the index of the list;
3.Generate random number inside range [0, i] assume 
  the random number is j;
4.If j==0, the random number is inside the reservoir     
  range, update the result to current ListNode's 
  value; 

class Solution {

    private ListNode head;
    private Random random;

    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }

    public int getRandom() {
        int result = head.val;
        int i = 2;
        ListNode curr = head.next;

        while (curr != null) {
            if (random.nextInt(i) == 0) {
                result = curr.val;
            }
            ++i;
            curr = curr.next;
        }
        return result;
    }
}