Randomized Sampling & Shuffling

Two deceptively simple questions this subtopic answers

"Pick one random element from a stream of unknown (or unbounded) length, so that every element had an exactly equal chance of being picked — without ever knowing the total length in advance, and without storing the whole stream."
"Shuffle a fixed array so that every one of the n! possible orderings is equally likely — not just 'looks pretty random.'"

Both have a correct, well-known O(n)-time, O(1)-extra-space answer, and both have a "looks right, is subtly and provably biased" wrong answer that shows up constantly in real code. Interviewers who ask these are almost always specifically probing for whether you know the difference.

Fisher–Yates shuffle: the only correct simple answer

To shuffle an array of n elements uniformly at random, walk from the last index to the first, and at each position, swap it with a uniformly random element from among the remaining unshuffled positions (including itself):

import random

def fisher_yates_shuffle(arr):
    for i in range(len(arr) - 1, 0, -1):
        j = random.randint(0, i)   # inclusive of i itself
        arr[i], arr[j] = arr[j], arr[i]
    return arr

Why this produces exactly each of the n! permutations with equal probability: at each step, position i receives one of i + 1 equally likely values, independent of every other step's choice — the total number of distinct execution paths is n * (n-1) * ... * 1 = n!, matching the number of permutations exactly, with each one reachable via exactly one sequence of random choices. This is O(n) time, O(1) extra space (an in-place shuffle), and it's the standard library implementation behind random.shuffle (Python), Collections.shuffle (Java), and equivalents in virtually every language.

The bug that keeps showing up in production: "random sort"

The naive, tempting alternative — sort the array using a comparator that returns a random value each time it's called — looks plausible and is genuinely, provably not a uniform shuffle:

# BROKEN: do not use — included to show exactly what goes wrong
import random
arr.sort(key=lambda x: random.random())

The problem isn't that this fails to run; it's that comparison-based sorting algorithms make a bounded number of comparisons (O(n log n) for most, and even fewer for small n) and the resulting permutation's probability distribution is an artifact of which specific comparisons the sort algorithm happens to make and in what order — not a clean, uniform draw over all n! permutations. Concretely: with n=3 elements, there are 3! = 6 possible orderings, but a comparison sort with a random comparator making, say, 2–3 comparisons total simply cannot produce 6 equally likely outcomes from that few random bits in a way that's provably uniform — some permutations end up systematically more likely than others, and the exact bias depends on the specific sort algorithm's comparison pattern. This is a real, documented category of bug (multiple popular libraries and interview solutions have shipped exactly this "shuffle," and analyses of it circulate specifically because the bias is subtle enough to pass casual testing while still being measurably, provably wrong under statistical scrutiny). The takeaway to state confidently in an interview: "shuffle" is not a sorting problem, and reaching for sort() with a random key is a tell that reads as a red flag to anyone who's seen this failure mode before.

Reservoir sampling: a fair sample from a stream of unknown length

Algorithm R solves "pick one uniformly random element from a stream, without knowing its length in advance, using O(1) extra space": keep the first element as your current pick; for every subsequent element at position i (1-indexed), replace your current pick with it with probability 1/i.

import random

def reservoir_sample_one(stream):
    result = None
    for i, item in enumerate(stream, start=1):
        if random.randint(1, i) == 1:   # probability 1/i
            result = item
    return result

Why element i ends up as the final answer with probability exactly 1/n (for a stream of total length n, even though you don't know n while running): element i is chosen at step i with probability 1/i, and then must survive every subsequent step without being replaced — surviving step j > i happens with probability 1 - 1/j = (j-1)/j. Multiplying these survival probabilities telescopes cleanly:

P(i is final answer) = (1/i) * (i/(i+1)) * ((i+1)/(i+2)) * ... * ((n-1)/n) = 1/n

Every intermediate numerator cancels the previous term's denominator, leaving exactly 1/n — independent of i. This telescoping-probability argument is worth being able to reproduce, since "why does this work" is a very natural, very common follow-up once you've stated the algorithm.

Generalizing to k samples: keep the first k elements as your initial reservoir; for each subsequent element at position i > k, include it with probability k/i, and if included, evict a uniformly random existing reservoir member to make room. The same telescoping argument generalizes to show every element ends with probability exactly k/n of being in the final sample.

import random

def reservoir_sample_k(stream, k):
    reservoir = []
    for i, item in enumerate(stream, start=1):
        if i <= k:
            reservoir.append(item)
        else:
            j = random.randint(1, i)
            if j <= k:
                reservoir[j - 1] = item
    return reservoir

Real-world case study: why this matters beyond interview problems

Reservoir sampling is the standard technique for sampling from data sources where the full size genuinely isn't known up front or is too large to materialize — a live log stream, a distributed MapReduce/Spark job scanning a dataset larger than memory, or any "give me a representative random sample of everything that will ever flow through this pipe" requirement in analytics tooling. It's the direct answer to "how do you take a fair random sample when you can't fit the whole population in memory and can't do a second pass" — a genuinely common constraint in streaming/big-data systems, not a contrived interview setup.

Comparison and complexity

	Time	Space	Requires knowing n in advance?
Fisher–Yates shuffle	O(n)	O(1) extra (in-place)	Yes — operates on a fixed array
Reservoir sampling (1 item)	O(n) — one pass	O(1)	No — works on an unbounded/unknown-length stream
Reservoir sampling (k items)	O(n) — one pass	O(k)	No
"Random sort" comparator shuffle	O(n log n)	O(n)	Yes, and it's wrong regardless

Pitfalls and interview gotchas

Off-by-one in Fisher–Yates's random range. random.randint(0, i) must be inclusive of i itself (the current position can legitimately swap with itself) — excluding it silently biases the distribution, since position i's own original value would then never have a chance to stay in place.
Shuffling with a comparator and a random key. As detailed above, this is a real, provably non-uniform bug — always implement Fisher–Yates explicitly rather than reaching for sort().
Reservoir sampling with the wrong replacement probability. It must be exactly 1/i (not 1/n, which you don't know yet, and not a fixed constant) at each step — getting this wrong breaks the uniformity guarantee even though the code still "runs" and produces some sample.
Forgetting reservoir sampling assumes each item is seen exactly once, in a single pass. If random access to re-sample is available (the data fits in memory and you know its length), Fisher–Yates followed by taking the first k elements is simpler and just as correct — reservoir sampling's whole value is for the streaming/unknown-length case specifically.

How to talk about this in an interview

"For shuffling a fixed array, I'll use Fisher–Yates — walk backward, swap each position with a uniformly random remaining position — which is provably uniform over all n! permutations; sorting with a random comparator looks similar but is provably biased, since a bounded number of comparisons can't produce a clean uniform draw over that many orderings. For sampling from a stream whose length I don't know in advance, I'd use reservoir sampling — replace the current pick with the ith element with probability 1/i — which I can show is uniform via a telescoping-probability argument, and it only needs a single pass and O(1) space."

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Shuffle an ArrayMedium!!2/520m
Linked List Random NodeMedium!!2/520m