Randomized Algorithms: Shuffling, Sampling and Random Choices

Interviewers like randomness questions because they are short to state, easy to get subtly wrong, and test whether you can argue about probability: "shuffle an array", "pick a random node from a linked list of unknown length", "pick an index with probability proportional to its weight", "build rand10 from rand7", "insert, delete and get a random element in O(1)". Random choices also make ordinary algorithms faster and safer, from quicksort pivots to hashing that adversarial inputs cannot break.

Intuition

• Pseudo-random generators are deterministic sequences that look random. A fixed seed reproduces the same run, which is useful for tests. They are not suitable for security; Python's secrets module and the operating system's generator are.
• Uniformity is the whole game. The standard trap is mapping a range onto a smaller one with %: if 7 equally likely values are reduced with % 5, the values 0 and 1 come up twice as often as the others. Either the number of equally likely outcomes divides evenly, or you reject the leftovers and try again (rejection sampling).
• Two kinds of randomized algorithms:
  • Las Vegas: always correct, running time is random (randomized quicksort, quickselect). Random pivots make the worst case vanishingly unlikely for every input, including adversarial ones.
  • Monte Carlo: fixed running time, small chance of a wrong answer (random hashing, fingerprints, randomized checks). Running k independent trials shrinks an error probability p to p^k.
• Proving a sampler correct usually means showing that every outcome is produced by the same number of equally likely random-choice sequences, or computing each element's survival probability.

When to use it in interviews / OAs

• Shuffle a list, deal cards, generate a random permutation: Fisher-Yates.
• Choose k items uniformly from a stream or a linked list whose length is unknown, in one pass and O(k) memory: reservoir sampling.
• Choose an index with probability proportional to a weight, or sample from a discrete distribution: prefix sums plus binary search.
• Build one uniform generator from another (rand7 to rand10, fair coin from a biased coin), or sample uniformly from an irregular region (random point in a circle): rejection sampling.
• Design a container with O(1) random access to its elements: an array plus a hash map of positions.
• Avoid worst cases on adversarial inputs: random pivots, randomly shuffled input, hashing with a random seed.
• Compare sets or multisets of large objects quickly: random fingerprints (sums of random weights, rolling hashes with a random base).

Template

Fisher-Yates shuffle

import random


def shuffle(a: list, rng=random) -> None:
    """Uniformly random permutation, in place."""
    for i in range(len(a) - 1, 0, -1):
        j = rng.randint(0, i)  # any position in a[0..i], inclusive, including i itself
        a[i], a[j] = a[j], a[i]

There are n * (n - 1) * ... * 2 = n! equally likely choice sequences, and each produces a different permutation, so every permutation has probability 1/n!. Drawing j from the whole array at every step instead gives n^n sequences, which is not divisible by n!, so that version is biased.

Reservoir sampling

def reservoir_sample(stream, k: int, rng=random) -> list:
    """k uniformly random items from an iterable of unknown length, one pass, O(k) memory."""
    sample = []
    for i, item in enumerate(stream):
        if i < k:
            sample.append(item)
        else:
            j = rng.randint(0, i)  # item i enters with probability k / (i + 1)
            if j < k:
                sample[j] = item   # and evicts a uniformly random current member
    return sample

Why it works: after processing i + 1 items, each of them is in the sample with probability k / (i + 1). A new item enters with exactly that probability; an existing member survives the step with probability 1 - (k / (i + 1)) * (1 / k) = i / (i + 1), which turns k / i into k / (i + 1). With k = 1 this is the "random node of a linked list" question.

Weighted random pick

from bisect import bisect_left
from itertools import accumulate


class WeightedPicker:
    """Pick index i with probability w[i] / sum(w), for positive integer weights."""

    def __init__(self, w: list[int], rng=random):
        self.prefix = list(accumulate(w))  # prefix[i] = w[0] + ... + w[i]
        self.rng = rng

    def pick(self) -> int:
        ticket = self.rng.randint(1, self.prefix[-1])  # a ticket number in 1..total
        return bisect_left(self.prefix, ticket)        # the first index whose prefix reaches it

Index i owns exactly w[i] of the tickets, those in (prefix[i - 1], prefix[i]]. With integer weights this is exact; with real weights use rng.random() * total and bisect_right.

Rejection sampling: rand10 from rand7

def rand10(rand7) -> int:
    """Uniform integer in 1..10 from a uniform 1..7 generator."""
    while True:
        idx = (rand7() - 1) * 7 + rand7()  # uniform in 1..49
        if idx <= 40:                      # keep 40 = 4 * 10 outcomes, reject the other 9
            return (idx - 1) % 10 + 1

Each attempt succeeds with probability 40/49, so the expected number of rand7 calls is 2 * 49/40, about 2.45.

Insert, delete and get a random element in O(1)

A hash set cannot return a uniformly random element in O(1); an array can, but deleting from its middle is O(n). Keep both: the array holds the values, the map holds each value's index, and deletion moves the last element into the hole:

class RandomizedSet:
    def __init__(self, rng=random):
        self.items: list[int] = []
        self.pos: dict[int, int] = {}  # value -> index in items
        self.rng = rng

    def insert(self, x: int) -> bool:
        if x in self.pos:
            return False
        self.pos[x] = len(self.items)
        self.items.append(x)
        return True

    def remove(self, x: int) -> bool:
        if x not in self.pos:
            return False
        i, last = self.pos[x], self.items[-1]
        self.items[i], self.pos[last] = last, i  # move the last element into the hole
        self.items.pop()
        del self.pos[x]
        return True

    def get_random(self) -> int:
        return self.items[self.rng.randrange(len(self.items))]

Random fingerprints: are two subarrays permutations of each other?

Give every distinct value an independent random 64-bit weight. Equal multisets have equal weight sums; different multisets collide only with negligible probability. Prefix sums of the weights then answer each query in O(1):

def make_multiset_checker(a: list[int], rng=random):
    """Monte Carlo test whether a[l1..r1] and a[l2..r2] contain the same values with the same counts."""
    mask = (1 << 64) - 1
    weight: dict[int, int] = {}
    prefix = [0]
    for x in a:
        if x not in weight:
            weight[x] = rng.getrandbits(64)
        prefix.append((prefix[-1] + weight[x]) & mask)

    def same(l1: int, r1: int, l2: int, r2: int) -> bool:
        h1 = (prefix[r1 + 1] - prefix[l1]) & mask
        h2 = (prefix[r2 + 1] - prefix[l2]) & mask
        return r1 - l1 == r2 - l2 and h1 == h2

    return same

The same trick (random weights or a random hash base) defeats test data crafted to collide with a fixed hash function.

Complexity

• Fisher-Yates: O(n) time, O(1) extra space.
• Reservoir sampling: O(n) time for n items, O(k) space.
• Weighted pick: O(n) preprocessing, O(log n) per pick.
• rand10: expected O(1) time, unbounded in the worst case (that is unavoidable: 10 does not divide any power of 7).
• RandomizedSet: O(1) average per operation.
• Multiset fingerprints: O(n) preprocessing, O(1) per query, error probability about q / 2^64 for q queries.

Common pitfalls

• Modulo bias: randint(0, big) % n is not uniform unless n divides the range size. Use randrange(n), or reject the leftovers.
• The naive shuffle that swaps each position with a random index from the entire array is biased.
• Off-by-one in reservoir sampling: randint(0, i) is inclusive and i is 0-based; using randint(0, i - 1) or randint(1, i) skews the probabilities.
• Floating-point weights: cumulative float sums are fine for sampling but need bisect_right on random() * total and care when weights can be zero.
• Forgetting to update the moved element's index in the O(1) random set.
• Testing random code with random tests only. Inject the generator, as above, so tests can feed fixed choices or a seeded random.Random, and check exact counts instead of eyeballing distributions.
• Using random for tokens or passwords. Use secrets.

Interview variations

• Shuffle an array (reset to the original on demand: keep a copy).
• Linked list random node and random pick index among duplicates: reservoir sampling with k = 1.
• Random pick with weight, random point in non-overlapping rectangles (weight each rectangle by its point count).
• Random pick with blacklist: remap blacklisted values in [0, n - b) to allowed values at the end so one randrange suffices.
• Implement rand10 using rand7, generate a random point inside a circle (rejection from the bounding square, or radius R * sqrt(u) for uniform area).
• Insert delete get-random O(1), also with duplicates (map each value to a set of indices).
• Kth largest with random pivots, randomized quicksort: Las Vegas algorithms with expected guarantees.
• Python helpers: random.shuffle, random.sample(population, k), random.choices(population, weights=w, k=k), random.randrange, and random.Random(seed) for reproducible runs.