Week 55 of 125
TAOCP 3.4.2 Random Sampling and Shuffling
Sign up or sign in to tick these off and give this week a due date.
-
Picking n records at random from N, both when N is known (selection sampling) and when it is not known in advance (reservoir sampling), and shuffling an array uniformly.
Time About 6 hours this week
Why it matters
Reservoir sampling and the Fisher-Yates shuffle are must-know algorithms. Getting the shuffle subtly wrong is a famous bug in real products.
Before you start
- 3.4.1 Numerical Distributions
How to approach it
Implement the shuffle and verify by running it a million times on a 3-element array and counting all 6 outcomes. Then implement the "naive" swap-with-any-position shuffle and see its bias. Implement reservoir sampling over a stream read from stdin.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Swapping with a random index from the whole array instead of the remaining part. That gives a biased shuffle.
- Off-by-one on the range of the random index.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.