2
$\begingroup$

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:

  1. Store the first node in the additional space.
  2. Move to the next node.
  3. Randomly select one node between the one in the additional space and the current node.
  4. Store this "winner" in the additional space.
  5. Repeat steps 2-4 until the last node in the list is processed.
  6. 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:

  1. Select 1 -> from (1, 2) select 1 -> from (1, 3) select 1 -> 1 is finally selected
  2. Select 1 -> from (1, 2) select 1 -> from (1, 3) select 3 -> 3 is finally selected
  3. Select 1 -> from (1, 2) select 2 -> from (2, 3) select 3 -> 3 is finally selected
  4. 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?

$\endgroup$
2
$\begingroup$

You are absolutely right.

Part of the problem with your friend's solution is that, when he instructs you to make a random choice (in line 3), he did not specify what probability you should use. It's his job to completely specify the algorithm, and not omit details like that. If we choose uniformly at random from the two options, then the algorithm does not work, for the reasons you describe.

It is possible to repair the algorithm by choosing appropriate probabilities at each iteration, but doing this right requires some care.

The standard solution to this is reservoir sampling. (See also Reservoir Sampling - Sampling from a stream of elements for another description of the same algorithm.) You can view reservoir sampling as an instance of your friend's algorithm, but with the probabilities for each random choice specified fully and worked out carefully so that the algorithm does meet the requirements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.