~/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.
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.
7 problems
Quant & trading
Probability Expected value, sampling, randomized algorithms.
Randomized algorithms
- Basics: weighted random pick basics easy
- Plant swap: nobody keeps their own cutting easy
- Random node of a linked list medium
- Shuffle an array easy
- Random index of a target value easy
- Random pick avoiding a blacklist medium
- Uniform sample of k items from a stream medium