~/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.
Probability and expected value
Linearity of expectation, conditioning, Markov-chain equations; answers as fractions.
Notes
Tools
- Linearity of expectation: E[X + Y] = E[X] + E[Y] even when X and Y are dependent. Use indicator variables for "expected number of X".
- Geometric distribution: with success probability p each try, the expected number of tries is 1/p.
- Conditioning / first-step analysis: write E[state] in terms of the next states and solve the linear equations. For HH, E0 = 1 + ½E1 + ½E0 and E1 = 1 + ½·0 + ½E0, which gives 6 (HT takes 4).
- Symmetry: often gives the answer with no computation at all.
Classics
- Coupon collector: n·H(n).
- Gambler's ruin with a fair coin, starting at i and aiming for N: P(win) = i/N.
- Expected rolls until a 6: 6.
- Expected maximum of two dice: 161/36.
- Birthday problem: about 23 people for a 50% chance.
In code: use fractions.Fraction for exact answers, and a quick Monte Carlo to sanity-check.
11 problems
Quant & trading
Probability Expected value, sampling, randomized algorithms.
Probability and expected value
- Basics: distribution of a dice sum basics easy
- Surprise scoops: expected flavours tried easy
- Uniform 1..10 from a 1..7 die medium
- New 21 Game py · c++ · java medium
- Knight stays on the board py · c++ · java medium
- Restart strategies for a random solve time 3 levels OpenAI hard
- Optimal execution with a broker backstop Optiver py · c++ · java hard
- Coupon collector: rolls until every face appears easy
- Expected coin flips until a pattern appears medium
- Expected maximum of k dice easy
- Gambler's ruin: chance to reach the target easy