The Question: You are given a singly-linked list with n nodes that you can only iterate through once at most. You are given additional space to store one node (i.e. a pointer to it). Devise an algorithm that can operate under these conditions, choose/select one node from the list such that the the probability of each node being selected/chosen is equal.
My Friend's Solution:
- Store the first node in the additional space.
- Move to the next node.
- Randomly select one node between the one in the additional space and the current node.
- Store this "winner" in the additional space.
- Repeat steps 2-4 until the last node in the list is processed.
- The node stored in the additional space at the end is the one that the algorithm selects.
My Issue With My Friend's Solution: Consider the case n = 3. There are 2^*(n-1) = 2^2 = 4 possible ways to go through the list in terms of which node is selected during each iteration of the algorithm:
- Select 1 -> from (1, 2) select 1 -> from (1, 3) select 1 -> 1 is finally selected
- Select 1 -> from (1, 2) select 1 -> from (1, 3) select 3 -> 3 is finally selected
- Select 1 -> from (1, 2) select 2 -> from (2, 3) select 3 -> 3 is finally selected
- Select 1 -> from (1, 2) select 2 -> from (2, 3) select 2 -> 2 is finally selected
Then, node 3 has a 50% chance of being selected, whereas nodes 1 and 2 each have a 25% chance of being selected.
Intuitively, this makes sense to me; if the first node is not selected while the beginning of the list is being processed, it can never be the one that is finally selected. However, the last node still has a chance of being selected no matter what happens while processing the the rest of the list that comes before the last node.
However, my friend says that my issue with his solution is inconsequential because I didn't model the situation correctly. Can someone tell me where I went wrong?