AdvancedMath for DSALinked List
Picking at random fairly: reservoir sampling
Don't know the length? Keep the i-th item with probability 1/i. Every item ends up chosen with exactly 1/n chance, in one pass.
The idea
To pick uniformly from a stream (or a linked list you can't index), keep a current choice. When you see the i-th item, replace the choice with probability 1/i.
Why it's fair: item i is picked at step i with chance 1/i, then survives each later step j with chance (1 − 1/j). Multiply: 1/i × i/(i+1) × … × (n−1)/n = 1/n. The same “each one equally likely” thinking underlies a correct shuffle (Fisher–Yates).
Worked example
Stream a, b, c
- a: keep with 1/1 → choice a.
- b: replace with 1/2 → a or b, each 1/2.
- c: replace with 1/3 → c is 1/3; a and b each 1/2 × 2/3 = 1/3.
In code (Python)
import random
def pick_random(head): # Linked List Random Node
choice, i, node = None, 0, head
while node:
i += 1
if random.randrange(i) == 0: # probability 1/i
choice = node.val
node = node.next
return choice
def shuffle(nums): # Fisher–Yates
for i in range(len(nums) - 1, 0, -1):
j = random.randint(0, i)
nums[i], nums[j] = nums[j], nums[i]
return numsO(n) time, O(1) space.
How to spot it
- “random node / index with equal probability”, unknown or huge input length, “shuffle”.
Common mistakes
- Shuffling with j from the whole array each time: it looks random but isn't uniform.
- Counting the length first when one pass is enough.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →