382. Linked List Random Node
Description:
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.
Implement the Solution
class:
Solution(ListNode head)
Initializes the object with the integer array nums.int getRandom()
Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.
Example:
1  Input 
Constraints:
 The number of nodes in the linked list will be in the range
[1, 104]
. 10^4 <= Node.val <= 10^4
 At most
10^4
calls will be made togetRandom
.
Since at most 10k calls will be made, the overall time complexity of each random call is expected to be bounded by O(nlogn).
Intuition:
A simple approach would be converting the linked list into an array, and then random generate a number and random access the array. This would cost extra O(n)
space for keeping an array, and O(1)
to random access the array.
Actually, another implementation is that, we could traverse the list to get the length, and then random generate a number, and then take O(n) step to get the number.
This implementation would take O(1) extra space, and O(n) for traversing and accessing.
What if… just visit each node only once and use O(1) space?
The key is, Each node must have the same probability of being chosen.
So to ensure the same probability, it is not necessary to use the builtin random function.
Introducing Reservoir Sampling:
I found a video on YouTube, explaining this idea in an interesting and great way.
Scenario: A man picking a hat
each round replace the old hat or wear new hat
Each round probability of wearing new hat: 1/n
The first hat has a chance of 1/1, so he 100% wear the hat
The second hat has a chance of 1/2, so he 50% wear the 2nd hat, 50% keep the first hat
The third hat has a chance of 1/3, 1/3 wear the 3nd hat, 2/3 keep the original hat
So on and so forth…
The Good Side:
Reservoir sampling doesn’t need to know the length of the list in advance, it’s an online random algorithm.
Proof on Equal Probability:
The $i_{th}$ hat has a probability of $\frac{1}{i}$ of being chosen in its round. The probability of $i_{th}$ hat being chosen after $n$ times can be given as:
Which is the multiplication of $i_{th}$ hat being chosen, and all the hats after $i_{th}$ hat not being chosen.
And this RHS equals to $\frac{1}n$, which means every hat has the same probability of being chosen.
Implementation:
Now let’s implement the Reservoir Sampling into our code, note that we still have to simulate the process of spinning the wheel, using the random function to implement. And it’s generally slower to perform floating point division, use integer instead.
 Instead of
1/i
, we have1,2,3…i
, but only the1
means being chosen i
start from1
, because it’s not valid to divide by 0.
1 
