Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
Example:
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
Solution 1: Reservior sampling: (wiki introduction)
Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing 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.
example: size = 1
Suppose we see a sequence of items, one at a time. We want to keep a single item in memory, and we want it to be selected at random from the sequence. If we know the total number of items (n), then the solution is easy: select an index i between 1 and n with equal probability, and keep the i-th element. The problem is that we do not always know n in advance. A possible solution is the following:
- Keep the first item in memory.
- When the i-th item arrives (for i>1):
- with probability 1/i, keep the new item (discard the old one)
- with probability 1-1/i, keep the old item (ignore the new one)
So:
- when there is only one item, it is kept with probability 1;
- when there are 2 items, each of them is kept with probability 1/2;
- when there are 3 items, the third item is kept with probability 1/3, and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
- by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) { val = x; }
7 * }
8 */
9 public class Solution {
10 ListNode start;
11
12 /** @param head The linked list's head.
13 Note that the head is guaranteed to be not null, so it contains at least one node. */
14 public Solution(ListNode head) {
15 this.start = head;
16 }
17
18 /** Returns a random node's value. */
19 public int getRandom() {
20 Random random = new Random();
21 ListNode cur = start;
22 int val = start.val;
23
24 for (int i=1; cur!=null; i++) {
25 if (random.nextInt(i) == 0) {
26 val = cur.val;
27 }
28 cur = cur.next;
29 }
30 return val;
31 }
32 }
33
34 /**
35 * Your Solution object will be instantiated and called as such:
36 * Solution obj = new Solution(head);
37 * int param_1 = obj.getRandom();
38 */
PROBLEM:
- Choose
entries fromk
numbers. Make sure each number is selected with the probability ofn
k/n
BASIC IDEA:
-
first and put them into the reservoir.1, 2, 3, ..., k
- For
, pick it with a probability ofk+1
, and randomly replace a number in the reservoir.k/(k+1)
-
k+i
k/(k+i)
- Repeat until
reachesk+i
n
PROOF:
-
, the probability that it is selected and will replace a number in the reservoir isk+i
k/(k+i)
- For a number in the reservoir before (let's say
), the probability that it keeps staying in the reservoir isX
-
×P(X was in the reservoir last time)
P(X is not replaced by k+i)
- =
× (P(X was in the reservoir last time)
-1
)P(k+i is selected and replaces X)
-
× (k/(k+i-1)
1
k/(k+i)
)1/k
-
k/(k+i)
-
- When
k+i
, the probability of each number staying in the reservoir isn
k/n
EXAMPLE
-
numbers from3
. Make sure each number is selected with a probability of[111, 222, 333, 444]
3/4
- First, choose
as the initial reservior[111, 222, 333]
- Then choose
with a probability of444
3/4
-
, it stays with a probability of111
-
+P(444 is not selected)
P(444 is selected but it replaces 222 or 333)
-
1/4
*3/4
2/3
-
3/4
-
- The same case with
and222
333
- Now all the numbers have the probability of
to be picked3/4