question
Given a linked-list with unknown length, randomly select one node with equal probability for every node in the list.
Look into reservoir sampling.
The most efficient solution will involve using reservoir sampling to maintain equal probability for each element in the list.
In this code we generate a random number between 0 and 1. If the number is less than 1/i than we select it. The first number in the list is selected prior to the main algorithm. We can see how each element has a 1/i probability of staying in the reservoir/assigned selection. The probability that each element stays in the reservoir given it is already in the reservoir is thus (i - 1)/i and the overall probability of each element being selected after i rounds is 1/i.
The explanation above is essentially a brief explanation of reservoir sampling. For a more thorough explanation see this excellent resource as well as the obligatory wikipedia article.
Thoughts or alternate solution? Let us know in the comments below!
int i = 2;
selection = headNode;
currentNode = headNode -> next;
while currentNode != null
if (random(0,1) < 1/i ) // Random number is exclusive from 0 to 1
selection = currentNode;
currentNode = currentNode->next;
i++;
return selection;
In this code we generate a random number between 0 and 1. If the number is less than 1/i than we select it. The first number in the list is selected prior to the main algorithm. We can see how each element has a 1/i probability of staying in the reservoir/assigned selection. The probability that each element stays in the reservoir given it is already in the reservoir is thus (i - 1)/i and the overall probability of each element being selected after i rounds is 1/i.
The explanation above is essentially a brief explanation of reservoir sampling. For a more thorough explanation see this excellent resource as well as the obligatory wikipedia article.
Thoughts or alternate solution? Let us know in the comments below!