Randomised Algorithms: Las Vegas, Monte Carlo, Random Pivots, Miller-Rabin, Karger and Reservoir Sampling

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 58m

At 2 a.m. in Lisbon, a fictional ticketing company's servers melt under a few dozen carefully crafted requests. Fixing the hash table leads us through the whole toolkit of randomised algorithms, from Ulam's solitaire at Los Alamos to the 2011 hash-flooding disclosures in Berlin and the 2002 "PRIMES is in P" result.

Chapters

00:00:00 Cold open: the request that took forty minutes

00:03:35 What a random algorithm is, and is not

00:06:29 Las Vegas and Monte Carlo

00:09:44 Quicksort and the pivot

00:13:59 Shuffling and the danger of doing it wrong

00:16:05 Is this number prime?

00:18:47 Miller…