~/boss / lucky-pick
Reservoir sampling
The Endless Parade
Hold one monster. Make sure every monster had the same chance.
Loading the fight…
How to beat it
Keep the first monster. Monster number i swaps into your slot with chance 1 in i: the second 1 in 2, the third 1 in 3. Then every monster so far is equally likely to be the one you hold, however long the stream runs.
Now the real boss
Interviews ask for the code. Watch it run, then write it yourself, tested in Python, C++ or Java.
On your phone? Writing code is easier on a laptop: open bossfight.dev/problems/linked-list-random-node there. Sign in with your email to keep your progress on every device.