~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Randomized algorithms
Reservoir sampling, Fisher-Yates, rejection sampling.
Main path: 8 problems, about 3 hours.
Notes
- Reservoir sampling (k items from a stream of unknown length): keep the first k. For the i-th item (1-indexed, i > k), pick
j = randrange(i), and ifj < k, replaceres[j]. Each item ends up kept with probability k/n. - Fisher-Yates shuffle:
for i in range(n - 1, 0, -1): j = randrange(i + 1); a[i], a[j] = a[j], a[i]. Usingrandrange(n)instead is biased, because n^n doesn't divide evenly by n!. - Rejection sampling: rand10 from rand7:
x = (rand7() - 1) * 7 + rand7()gives 1..49 uniformly. Accept values <= 40 and returnx % 10 + 1. - Random pick with a blacklist: remap the blacklisted values below the cutoff to allowed values above it.
8 problems
Advanced & competitive
Randomness Random sampling, shuffles and expected value.
Randomized algorithms
- Play first: The Endless Parade 1-minute game Reservoir sampling
- Roll a die and tally the faces basics py · c++ · java easy
- Plant swap: nobody keeps their own cutting py · c++ · java easy
- Shuffle an array py · c++ · java medium
- Insert Delete GetRandom O(1) py · c++ · java medium
- Random index of a target value py · c++ · java medium
- Random node of a linked list code the boss py · c++ · java medium
- Uniform sample of k items from a stream py · c++ · java medium
- Random pick avoiding a blacklist py · c++ · java hard