Randomized algorithms and sampling

intermediateCommon atGoogleMetaAnthropicTrading firmsRead firstHash maps Arrays Practise in the Sandbox →

A fair random process gives every outcome the same number of equally likely paths. Fisher-Yates shuffles in O(n) by picking each position’s item from the not-yet-placed part only. Reservoir sampling keeps k uniform picks from a stream of unknown length by keeping item i with chance k/(i+1). A dense array plus a value→index map gives O(1) insert, delete and random pick, because delete fills the hole with the last element.

The idea in plain words

Drawing names from a hat is fair because every name has the same chance at every draw, and drawn names don’t go back in. Code that “feels random” often isn’t fair: it lets some outcomes happen in more ways than others.

The test for fairness is counting. If a shuffle of n items makes n! equally likely runs and each run produces a different ordering, every ordering has chance 1/n!. If it makes n^n runs, those can’t split evenly over n! orderings (for n ≥ 3), so some orderings must come up more often.

Randomized algorithms use randomness in two ways:

To produce a random result. Shuffle a deck, sample k rows, pick a random element.
To be fast on every input. Quicksort with a random pivot has no “bad input”; only bad luck, and bad luck is astronomically rare.

See it

Shuffling

Step through Fisher-Yates on your own items. Then run the simulation and compare it with the shuffle most people write first.

Fisher-Yates shuffle, and the shuffle that looks right

step through + simulate

items (2-10)seed

0123456

i–

j–

choices–

still unplaced: candidatespickedlocked in

Fisher-Yates fills the answer from the back. Each step picks one of the items not yet placed, uniformly, and moves it into the last open position.

1 / 14speed

Fisher-Yates vs "for each i, swap with a random index in 0..n−1"

Run it to compare how often each of the 6 orderings comes out.

Sampling a stream

You can’t see the whole stream, and you can’t store it. Step through one run, then replay ten thousand and check that every item is picked equally often. Switch the rule to the “obvious” fixed 50% and watch late items take over.

Reservoir sampling: k fair picks from a stream

step through + simulate

stream length n sample size k seed

stream (arrives left to right)

0123456789

reservoir (3 slots)

012

seen0

P(keep)–

roll–

arriving / slot writtenin the reservoirskippedevicted or skipped earlier

Items arrive one at a time and we never know how many are coming. Goal: at every moment, the 3 items in the reservoir are a uniform random sample of everything seen so far.

1 / 12speed

rule

Press run to replay the algorithm on 10,000 fresh streams and count how often each item ends up in the sample.

Random pick from a changing set

A hash set can insert and delete in O(1), but it can’t give you a uniformly random member in O(1): it has no “element number i”. An array can, but deleting from its middle is O(n). Combine them. Insert a few values, remove one from the middle, and watch where the last element goes.

Array + index map: O(1) insert, remove and random pick

sandbox

value

items (dense array: no gaps, so a random index is always a valid value)

012345

index map (value → position in items)

12→ 0

5→ 1

31→ 2

8→ 3

20→ 4

17→ 5

Pick a value, then insert or remove it. Removing from the middle is the interesting case: instead of shifting everything left, the last element jumps into the hole. Order is lost, but nothing in a set depends on order.

When to reach for it

The problem says…	Technique
“shuffle”, “random permutation”, “deal cards”	Fisher-Yates
“random sample of k from a stream / huge file / unknown length”	Reservoir sampling
“random element” plus inserts and deletes, all fast	Dense array + value→index map, swap-remove on delete
“k-th smallest”, “median” in expected linear time	Quickselect with a random pivot (divide and conquer)
an adversary could choose the input (hash flooding, sorted input to quicksort)	Randomize the pivot or the hash seed
“estimate”, “approximately”, huge data	Sampling, Monte Carlo, or sketches (Bloom filter, HyperLogLog)

How it works

Fisher-Yates (Knuth) shuffle

Walk i from the last index down to 1. Everything after i is already final.
Pick j uniformly from 0..i inclusive: only the unplaced items, and i itself.
Swap xs[i] and xs[j]. Position i is now locked.

Step 1 has n choices, the next n−1, and so on: n! equally likely runs, each giving a different ordering. That’s the proof.

import random
from collections import Counter


def fisher_yates(xs: list[int], rng: random.Random) -> None:
    """Shuffle in place so each of the n! orders is equally likely. O(n)."""
    for i in range(len(xs) - 1, 0, -1):    # 1. walk from the back; xs[i+1:] is already final
        j = rng.randint(0, i)              # 2. pick from the UNFIXED part only, 0..i inclusive
        xs[i], xs[j] = xs[j], xs[i]        # 3. lock xs[i] in; i itself is a legal pick


if __name__ == "__main__":
    rng = random.Random(42)                # seeded: reproducible tests
    deck = list(range(10))
    fisher_yates(deck, rng)
    assert sorted(deck) == list(range(10))
    # Uniformity: 60,000 shuffles of 3 items -> each of the 6 orders about 10,000 times.
    counts = Counter()
    for _ in range(60_000):
        trio = [0, 1, 2]
        fisher_yates(trio, rng)
        counts[tuple(trio)] += 1
    assert len(counts) == 6 and all(9_400 < c < 10_600 for c in counts.values())
    random.shuffle(deck)                   # stdlib does the same algorithm
    print("ok")

import assert from "node:assert/strict";

/** Shuffle in place so each of the n! orders is equally likely. O(n). JS has no built-in. */
export function fisherYates<T>(xs: T[], rand: () => number = Math.random): void {
  for (let i = xs.length - 1; i > 0; i--) { // 1. walk from the back; xs[i+1..] is already final
    const j = Math.floor(rand() * (i + 1)); // 2. pick from the UNFIXED part only, 0..i inclusive
    [xs[i], xs[j]] = [xs[j], xs[i]]; // 3. lock xs[i] in; i itself is a legal pick
  }
}

/** Small seeded PRNG (mulberry32) so tests are reproducible. */
function mulberry32(seed: number): () => number {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const rand = mulberry32(42);
const deck = Array.from({ length: 10 }, (_, i) => i);
fisherYates(deck, rand);
assert.deepEqual([...deck].sort((a, b) => a - b), Array.from({ length: 10 }, (_, i) => i));
// Uniformity: 60,000 shuffles of 3 items -> each of the 6 orders about 10,000 times.
const counts = new Map<string, number>();
for (let t = 0; t < 60_000; t++) {
  const trio = [0, 1, 2];
  fisherYates(trio, rand);
  counts.set(trio.join(""), (counts.get(trio.join("")) ?? 0) + 1);
}
assert.equal(counts.size, 6);
for (const c of counts.values()) assert.ok(c > 9_400 && c < 10_600);
console.log("ok");

// Shuffle in place so each of the n! orders is equally likely. O(n).
static void FisherYates<T>(T[] xs, Random rng)
{
    for (int i = xs.Length - 1; i > 0; i--) // 1. walk from the back; xs[i+1..] is already final
    {
        int j = rng.Next(i + 1);            // 2. pick from the UNFIXED part only, 0..i inclusive
        (xs[i], xs[j]) = (xs[j], xs[i]);    // 3. lock xs[i] in; i itself is a legal pick
    }
}

var rng = new Random(42);                   // seeded: reproducible tests
int[] deck = [.. Enumerable.Range(0, 10)];
FisherYates(deck, rng);
if (!deck.Order().SequenceEqual(Enumerable.Range(0, 10))) throw new Exception("not a permutation");

// Uniformity: 60,000 shuffles of 3 items -> each of the 6 orders about 10,000 times.
var counts = new Dictionary<string, int>();
for (int t = 0; t < 60_000; t++)
{
    int[] trio = [0, 1, 2];
    FisherYates(trio, rng);
    string key = string.Concat(trio);
    counts[key] = counts.GetValueOrDefault(key) + 1;
}
if (counts.Count != 6 || counts.Values.Any(c => c < 9_400 || c > 10_600)) throw new Exception("biased");
Random.Shared.Shuffle(deck);                // .NET 8+ built-in, same algorithm
Console.WriteLine("ok");

Stdlib: Python random.shuffle(xs) (in place) and random.sample(xs, k). .NET 8+ has Random.Shared.Shuffle(array) and Random.Shared.GetItems(choices, n) (with replacement). JavaScript has no built-in shuffle; xs.sort(() => Math.random() - 0.5) is biased, because sorting algorithms aren’t designed for inconsistent comparisons.

Reservoir sampling (Algorithm R)

Put the first k items straight into the reservoir.
For item i (0-based, i ≥ k), draw j uniformly from 0..i.
If j < k, item i replaces reservoir slot j. Otherwise skip it.

Why it’s fair: item i enters with chance k/(i+1). Afterwards, at each later step t it’s evicted only if the new item is kept (chance k/(t+1)) and lands on its slot (chance 1/k), so it survives that step with chance 1 − 1/(t+1) = t/(t+1). Multiply: k/(i+1) · (i+1)/(i+2) · … · (n−1)/n = k/n. The product telescopes.

import random
from collections import Counter
from collections.abc import Iterable


def reservoir_sample(stream: Iterable[int], k: int, rng: random.Random) -> list[int]:
    """k items chosen uniformly from a stream of unknown length, in one pass, O(k) memory."""
    sample: list[int] = []
    for i, x in enumerate(stream):
        if i < k:
            sample.append(x)               # 1. the first k items fill the reservoir
        else:
            j = rng.randint(0, i)          # 2. item i survives with probability k/(i+1)...
            if j < k:
                sample[j] = x              # 3. ...and evicts a uniformly random resident
    return sample


if __name__ == "__main__":
    rng = random.Random(7)
    assert reservoir_sample(range(2), 5, rng) == [0, 1]     # short stream: keep everything
    # Each of 10 items should land in a 3-item sample 30% of the time.
    hits = Counter()
    for _ in range(30_000):
        hits.update(reservoir_sample(range(10), 3, rng))
    assert all(8_500 < hits[v] < 9_500 for v in range(10))   # expected 9,000 each
    print("ok")

import assert from "node:assert/strict";

/** k items chosen uniformly from a stream of unknown length, in one pass, O(k) memory. */
export function reservoirSample<T>(stream: Iterable<T>, k: number, rand: () => number = Math.random): T[] {
  const sample: T[] = [];
  let i = 0;
  for (const x of stream) {
    if (i < k) sample.push(x); // 1. the first k items fill the reservoir
    else {
      const j = Math.floor(rand() * (i + 1)); // 2. item i survives with probability k/(i+1)...
      if (j < k) sample[j] = x; // 3. ...and evicts a uniformly random resident
    }
    i++;
  }
  return sample;
}

function* range(n: number): Generator<number> {
  for (let i = 0; i < n; i++) yield i; // a generator: length unknown up front, like a real stream
}

assert.deepEqual(reservoirSample(range(2), 5), [0, 1]); // short stream: keep everything
// Each of 10 items should land in a 3-item sample 30% of the time.
const hits = new Array<number>(10).fill(0);
for (let t = 0; t < 30_000; t++) for (const v of reservoirSample(range(10), 3)) hits[v]++;
for (const h of hits) assert.ok(h > 8_500 && h < 9_500, `got ${h}, expected ~9000`);
console.log("ok");

// k items chosen uniformly from a stream of unknown length, in one pass, O(k) memory.
static List<T> ReservoirSample<T>(IEnumerable<T> stream, int k, Random rng)
{
    var sample = new List<T>(k);
    int i = 0;
    foreach (T x in stream)
    {
        if (i < k) sample.Add(x);           // 1. the first k items fill the reservoir
        else
        {
            int j = rng.Next(i + 1);        // 2. item i survives with probability k/(i+1)...
            if (j < k) sample[j] = x;       // 3. ...and evicts a uniformly random resident
        }
        i++;
    }
    return sample;
}

var rng = new Random(7);
if (!ReservoirSample(Enumerable.Range(0, 2), 5, rng).SequenceEqual([0, 1])) throw new Exception("short stream");
// Each of 10 items should land in a 3-item sample 30% of the time.
var hits = new int[10];
for (int t = 0; t < 30_000; t++)
    foreach (int v in ReservoirSample(Enumerable.Range(0, 10), 3, rng)) hits[v]++;
if (hits.Any(h => h < 8_500 || h > 9_500)) throw new Exception("biased: " + string.Join(",", hits));
Console.WriteLine("ok");

O(1) random pick: array + index map

The building block from the sandbox above, in words:

State. items: a dense array with no gaps. pos: a hash map from value to its index in items.
Insert. Append to items, record pos[value] = last index. O(1) amortized.
Delete (the trick). Look up the index i of the value. Copy the last element into slot i, update that element’s entry in pos, then pop the end of the array and delete the removed value from pos. No shifting, so O(1). If the value was already last, just pop.
Random pick. items[randomInt(0, len)]. Every value occupies exactly one slot, so each has chance 1/len.

The price is order: after deletes, items is in no particular order. For a set that doesn’t matter. Two classic bugs: updating pos for the moved element after deleting the removed value’s key (wrong when they’re the same value, i.e. the removed one was last), and forgetting that the moved element’s index changed at all.

Random integers without bias

randomBits() % n is biased unless n divides the number of possible values: with 3-bit randoms (0-7) and n = 3, residues 0 and 1 get three values each, but 2 gets only two. Libraries fix this by rejection: throw away draws from the incomplete last block and redraw. Use the library: Python random.randrange(n), C# Random.Next(n), and in JS Math.floor(Math.random() * n) (fine for small n; its double has 53 random bits at most).

What it costs

	Time	Extra space	Note
Fisher-Yates	O(n)	O(1), in place	`n − 1` random draws
Partial Fisher-Yates (first k of n)	O(k)	O(n) to copy the input, or O(k) with a hash map of swapped slots	stop after k steps
Reservoir sampling, Algorithm R	O(n), one pass	O(k)	one random draw per item
Reservoir sampling, Algorithm L	O(k(1 + log(n/k))) expected draws	O(k)	skips ahead; worth it when n ≫ k
Array + index map	O(1) insert, delete, pick	O(n)	insert is amortized (array growth)

Expected vs worst case. Randomized quicksort is O(n log n) expected for every input; its worst case is still O(n²), but it needs a specific sequence of unlucky pivots with vanishing probability. Algorithms whose running time is random but whose answer is always correct are called Las Vegas (quicksort, quickselect). Ones whose running time is fixed but whose answer may be wrong with small probability are Monte Carlo (Miller-Rabin primality test, Bloom filters).

Variations you’ll meet

Random pivot. Quicksort and quickselect. Shuffling the input once does the same job.
Weighted sampling without replacement from a stream. Give each item the key u^(1/w) for a uniform u, keep the k largest keys in a heap (Efraimidis and Spirakis, 2006).
Random hashing. Python randomizes str hashes per process (PYTHONHASHSEED) and .NET Core randomizes string hash codes, so an attacker can’t precompute colliding keys. Universal hashing is the theory behind it.
Skip lists and treaps. Balanced search structures where random coin flips do the balancing; O(log n) expected.
Monte Carlo estimation. Throw random points, count hits. Error shrinks like 1/√(trials).
Seeded randomness for tests. Inject the random source (as the snippets do) so tests are reproducible.

Pitfalls

Off-by-one in Fisher-Yates. j must be in 0..i inclusive. Picking from 0..i-1 (Sattolo’s algorithm) only produces single-cycle permutations: no item can stay in place. Picking from 0..n-1 is the biased shuffle in the simulation.
Sorting with a random comparator. Biased, and in some languages it can even throw for an inconsistent comparator.
Creating a new RNG per call (new Random() in a loop on old .NET Framework). Seeds from the clock repeat. Reuse one instance, or Random.Shared.
Math.random() / random for security. Neither is cryptographically secure. Use crypto.getRandomValues / crypto.randomInt (JS), secrets (Python), RandomNumberGenerator (C#) for tokens and ids.
Testing randomness with exact equality. Assert properties (it’s a permutation) and loose frequencies over many trials, or inject a seeded generator.
Swap-remove ordering bugs (see above): handle “removed value was the last element”.

In the interview

Ask: “Does it need to be uniform? Is the input a stream? Can values repeat? Are there weights?”
Say the fairness argument, not just the code: “Each step picks from the remaining items, so there are n! equally likely runs.” For reservoir sampling, the telescoping product is a strong signal.
If a problem needs O(1) delete and O(1) random access, say why a set alone and an array alone each fail, then combine them.
Mention the seed: “I’ll inject the random source so the tests are deterministic.”
Expect follow-ups: weighted picks, picks without replacement, distributing the sample across machines (each machine samples k, then merge with weights), and “what if deletions are rare but picks are frequent?”

Check yourself

pick one

A shuffle loops i from 0 to n-1 and swaps xs[i] with xs[random index in 0..n-1]. Why must it be biased for n = 3?

Check yourself

pick one

Reservoir sampling with k = 1 has just seen its 5th item (i = 4). With what probability does that item replace the current pick?

Check yourself

pick one

With an array plus a value→index map, you remove value v at index i by moving the last element into slot i. Which step is easy to forget?

Practice on your own

Classic textbook exercises, not gym questions:

Return a random node from a singly linked list of unknown length in one pass.
Pick a random index of a given target value in an array with duplicates, using O(1) extra space.
Generate a uniform random point inside a circle (beware: random radius and angle is not uniform).
Implement rand7() using only rand5(), with rejection sampling.
Estimate π by Monte Carlo and plot how the error shrinks with the number of samples.

Go deeper

Donald Knuth, The Art of Computer Programming, Vol. 2, §3.4.2 “Random Sampling and Shuffling”: Algorithm P (shuffle) and reservoir sampling.
Jeffrey Vitter, “Random Sampling with a Reservoir”, ACM TOMS, 1985.
Mike Bostock, “Fisher-Yates Shuffle”, an animated explanation, and the biased-shuffle comparison at bost.ocks.org/mike/shuffle/compare.html.
Stdlib docs: Python random, .NET Random.Shuffle, MDN Crypto.getRandomValues.

Hash maps and setsThe other half of the O(1) random-pick structure.

Divide and conquerQuickselect and why random pivots work.

Prefix sumsTurn many small reads into one subtraction.

StreamingOne-pass algorithms over unbounded input.

Randomized algorithms and sampling

The idea in plain words

See it

Shuffling

Sampling a stream

Random pick from a changing set

When to reach for it

How it works

Fisher-Yates (Knuth) shuffle

Reservoir sampling (Algorithm R)

O(1) random pick: array + index map

Random integers without bias

What it costs

Variations you’ll meet

Pitfalls

In the interview

Check yourself

Practice on your own

Go deeper

Related