Lab 09 — Randomized Algorithms

Goal

Own the randomized toolkit interviews actually test: quickselect with random pivot (expected O(n)), Fisher–Yates shuffle, reservoir sampling for streams, and rejection sampling — plus the probability arguments interviewers push on when they ask “why is that uniform?” and “what’s the expected cost?”. Target: any of the four from blank in <10 minutes, each with its proof sketch on demand.

Background Concepts

Las Vegas vs Monte Carlo. Las Vegas: always correct, runtime is random (quickselect, quicksort). Monte Carlo: runtime fixed, correctness is probabilistic (Miller–Rabin, phase-13 lab-06; hashing checks). Know which you’re offering before the interviewer asks.

Quickselect expectation. A uniformly random pivot lands in the middle half with probability 1/2; conditioned on that, the surviving side is ≤ 3n/4. So the expected work satisfies T(n) ≤ n + T(3n/4)-in-expectation, giving T(n) ≤ n(1 + 3/4 + (3/4)² + …) = 4n = O(n). Worst case remains O(n²), with probability vanishing in n.

Fisher–Yates uniformity. For i from n−1 down to 1, swap a[i] with a[j], j uniform on [0, i] (inclusive — self-swap allowed). Induction: position n−1 receives each element with probability 1/n; conditioned on that, the remaining prefix is a uniform shuffle of n−1 elements. Each permutation: 1/n × 1/(n−1) × … = 1/n!.

Reservoir sampling. Keep the first k items; for item i (0-indexed, i ≥ k) draw j uniform on [0, i] and replace res[j] if j < k — keep probability k/(i+1). Induction: after item i, every item seen so far is in the reservoir with probability k/(i+1). One pass, O(k) memory, stream length unknown in advance.

Randomization as defense. A fixed-base rolling hash (phase-03 lab-06) is broken by published anti-hash tests; drawing the base randomly per run makes the adversary’s collision probability ≈ n²/(2p) — the birthday bound: expect a collision only after ~√p strings. Same principle: languages randomize hash seeds so attackers can’t precompute worst-case buckets.

Interview Context

LC 215 with “do better than O(n log n)” is the single most common randomized prompt; LC 384 is the uniformity-proof filter; LC 382/398 test whether “stream” triggers reservoir; LC 470 tests rejection sampling arithmetic. The differentiator is never the code — it’s whether you can defend uniformity and expected cost under pushback. Rehearse the three induction proofs above; interviewers at Google/Meta/quant shops ask for exactly them.

Problem Statement (LC 215, LC 384, LC 382, LC 398, LC 470)

• LC 215: k-th largest element in an array — expected O(n) quickselect.
• LC 384: Shuffle an Array — return uniformly random permutations; reset support.
• LC 382: random node of a singly linked list, unknown length, O(1) memory — reservoir k=1.
• LC 398: random index among positions where target occurs — reservoir over matches.
• LC 470: implement rand10() given rand7() — rejection sampling.

Constraints

• LC 215: n ≤ 10⁵, values fit in int; duplicates present.
• LC 384: n ≤ 200 but shuffle called up to 5×10⁴ times — per-call O(n).
• LC 382/398: single pass, O(1)/O(k) auxiliary memory; stream length unknown.
• LC 470: rand7 is the only entropy source; minimize expected calls.

Clarifying Questions

1. K-th largest with duplicates — by value rank or by sorted position? (Sorted position: sorted(a)[n−k].)
2. Can I mutate the input array? (Quickselect partitions in place; copy first if not.)
3. Does “uniform” mean every permutation equally likely, or every element equally likely per slot? (Every permutation — the stronger condition; slot-uniformity alone is weaker.)
4. Is the RNG assumed uniform and independent per call? (Yes; that’s the model all proofs rely on.)
5. Adversarial inputs — could someone feed a killer case? (Random pivot/seed makes the adversary blind; without randomization, sorted input kills naive quickselect.)
6. Stream too big for memory but k items fit? (Reservoir; if even k doesn’t fit, sample rate must be revisited.)

Examples

quickselect([3,2,1,5,6,4], k=2 largest) → 5
quickselect([3,2,3,1,2,4,5,5,6], k=4 largest) → 4
fisher_yates([0,1,2]) → each of the 6 permutations with probability 1/6
reservoir_sample(stream of 10 items, k=3) → each item kept with probability 3/10
rand10(): (rand7()−1)·7 + rand7() uniform on 1..49; accept ≤ 40, map (v−1) % 10 + 1

Initial Brute Force

• K-th largest: sort, index — O(n log n). Correct, and the oracle for everything below.
• Shuffle: generate a random permutation by sorting on random keys — O(n log n) and subtly wrong with duplicate keys.
• Random stream node: buffer the whole stream, pick uniformly — O(n) memory.

Brute Force Complexity

Sorting: O(n log n) time — fine until the interviewer says “linear expected time”. Buffering a stream: O(n) memory — disqualified by the O(1)-memory constraint, not by speed. The brute forces here fail on constraints, not correctness; keep them as oracles.

Optimization Path

1. Sort-based selection O(n log n) → heap of size k, O(n log k) → quickselect, expected O(n).
2. Full-buffer stream sampling O(n) memory → reservoir, O(k) memory, one pass.
3. Sort-by-random-key shuffle → Fisher–Yates: O(n), provably uniform, in place.
4. rand10 via rand7() % ... hacks (biased) → rejection sampling: exactly uniform, expected 2.45 calls.

Final Expected Approach

import random

def quickselect(nums, k):
    """k-th smallest (0-indexed), expected O(n). Iterative Lomuto, random pivot."""
    a = list(nums)
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        p = random.randint(lo, hi)                 # random pivot defeats adversaries
        a[p], a[hi] = a[hi], a[p]
        pivot, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]                  # pivot lands in final slot i
        if k == i:
            return a[i]
        if k < i:
            hi = i - 1
        else:
            lo = i + 1

def kth_largest(nums, k):                          # LC 215
    return quickselect(nums, len(nums) - k)

def fisher_yates(arr):                             # LC 384 core
    a = list(arr)
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)                   # [0, i] inclusive — self-swap allowed
        a[i], a[j] = a[j], a[i]
    return a

def reservoir_sample(iterable, k):                 # LC 382 / LC 398 generalized
    res = []
    for i, x in enumerate(iterable):
        if i < k:
            res.append(x)
        else:
            j = random.randint(0, i)               # keep x with probability k/(i+1)
            if j < k:
                res[j] = x
    return res

def rand7():
    return random.randint(1, 7)

def rand10():                                      # LC 470: rejection sampling
    while True:
        v = (rand7() - 1) * 7 + rand7()            # uniform over 1..49
        if v <= 40:
            return 1 + (v - 1) % 10                # 40 outcomes → exactly 4 per value

Data Structures Used

• Quickselect: the array itself plus two window pointers — no recursion stack (iterative).
• Reservoir: array of size k.
• rand10: none — just the two-digit base-7 construction.

Correctness Argument

Quickselect invariant: the k-th smallest of the whole array always lies in a[lo..hi], and partitioning is a permutation of that window. After Lomuto, a[i] = pivot with everything strictly smaller to its left, so exactly i elements are < pivot: if k = i we’re done (with duplicates, sorted(a)[i] must equal the pivot since positions 0..i−1 hold the < elements and the right side is ≥ pivot); otherwise recurse into the side containing k — the invariant is maintained.

Fisher–Yates: by downward induction as in Background — P(specific permutation) = Π 1/(i+1) = 1/n!.

Reservoir: induction on i. Base: first k items kept with probability 1. Step: item i survives insertion with probability k/(i+1) directly; a previous item survives with probability [k/i] · (1 − (k/(i+1)) · (1/k)) = k/(i+1). Uniform at every prefix — correct even though the stream length is never known.

rand10: the pair (r₁, r₂) is uniform over 49 outcomes, so v is uniform on 1..49. Conditioning on acceptance (v ≤ 40) keeps uniformity on 1..40, and 40 = 4 × 10 splits into equal preimage classes of size 4 per output. Rejection never biases; truncating with % 10 on 1..49 would (values 1..9 get 5 preimages, 10 gets 4).

Complexity

Implementation Requirements

• Quickselect must be iterative (no stack-depth surprises) and must pick the pivot uniformly from [lo, hi] — not a[hi] blindly.
• fisher_yates draws j on the inclusive range [0, i]; document it in a comment — this is the bug magnet.
• reservoir_sample must accept any iterable (generators included) and never call len().
• rand10 may only obtain randomness through rand7().
• All routines must behave correctly under duplicates (LC 215 tests this deliberately).

Tests

• Quickselect vs sorted(nums)[k] on 500 random arrays (n ≤ 60, heavy duplicates from range −20..20), plus both LC 215 examples.
• Shuffle: 60 000 shuffles of [0,1,2]; all 6 permutations observed, each count within ±600 of 10 000 (≈7.5σ — flags real bias, ignores noise).
• Reservoir: k=3 over a 10-item stream × 30 000 trials — every element’s inclusion count within ±600 of 9 000; stream shorter than k returns the whole stream.
• rand10: 100 000 draws — support exactly {1..10}, each count within ±700 of 10 000. (All executed for this lab; chi-square-style bucket tolerances chosen ≥ 4σ.)

Follow-up Questions

• Why is “sort by random key” or “swap each i with random j ∈ [0, n−1]” biased? → the n-random-swaps version has nⁿ equally likely execution paths but n! target permutations; n! ∤ nⁿ (e.g. 27 paths onto 6 permutations for n=3), so some permutation must be hit more often. Sort-by-key additionally collides keys. Fisher–Yates has exactly n! paths, one per permutation.
• Can selection be worst-case O(n)? → yes — median-of-medians (groups of 5) guarantees a 30/70 split, T(n) = T(n/5) + T(7n/10) + O(n) = O(n). But constants ≈ 10–20× random pivot; it’s a talking point and the theory answer, not the implementation. C++ nth_element uses introselect: random pivots with a median-of-medians fallback.
• Expected vs amortized vs high probability? → expected: average over the algorithm’s own coin flips, any input (quickselect O(n)). Amortized: worst-case total over an operation sequence, no randomness (vector doubling). W.h.p.: probability ≥ 1 − 1/nᶜ (quickselect exceeds c·n only with polynomially small probability). Interviewers probe whether you conflate them.
• Exact expected cost of rand10? → each round makes 2 rand7 calls and accepts with probability 40/49. Rounds are geometric: E[rounds] = 49/40, so E[calls] = 2 × 49/40 = 2.45. Follow-up: recycle the rejected entropy (v − 40 ∈ 1..9 is a free rand9) to push calls below 2.45.
• Why do languages randomize hash seeds? → hash-flooding DoS: with a public hash, an attacker POSTs 10⁵ keys colliding into one bucket, turning dict inserts O(n²). A per-process random seed (universal hashing: pick h from a family s.t. P(h(x)=h(y)) ≤ 1/m) makes collisions unpredictable. Identical to the anti-hash-test defense for rolling hashes (phase-03 lab-06).
• When is quickselect’s O(n²) tail acceptable? → when inputs aren’t adversarial and the RNG is unseeded by users, the tail probability is ~2⁻ᶜⁿ-ish in practice; for hard latency SLOs, use introselect or a k-size heap (O(n log k), worst-case, streaming-friendly).

Product Extension

Telemetry pipelines reservoir-sample k events per minute per service so downstream storage is O(k) regardless of traffic spikes — the exact LC 382 pattern with k > 1 and sharding. A/B assignment is Fisher–Yates thinking: hash(user_id, salt) mod buckets, salt rotated per experiment (the “random key” done right, deterministically replayable). Load balancers use “power of two random choices” — two random probes, pick the emptier — expected max load drops from Θ(log n/log log n) to Θ(log log n).

Language/Runtime Follow-ups

• Python: random is Mersenne Twister — fine for algorithms, never for tokens (use secrets). random.shuffle IS Fisher–Yates; random.sample does reservoir-adjacent selection without materializing when given a range.
• C++: rand() % n is biased and low-entropy; use std::mt19937_64 + uniform_int_distribution. std::shuffle requires a URBG; std::random_shuffle was removed in C++17 for exactly the bias reasons above. nth_element = introselect.
• Java: Collections.shuffle is Fisher–Yates; ThreadLocalRandom over shared Random under concurrency (CAS contention).
• Go: math/rand vs crypto/rand split mirrors Python; rand.Shuffle takes a swap closure — Fisher–Yates underneath.
• JS/TS: Math.random is unseedable and engine-dependent; sort(() => Math.random() − 0.5) is the canonical broken shuffle (comparison sorts assume consistent comparators — undefined behavior plus bias).

Common Bugs

1. Exclusive upper bound in Fisher–Yates: j ∈ [0, i−1] (no self-swap) is Sattolo’s algorithm — it generates only n-cycles, (n−1)! outcomes, never the identity. Tests that only check “looks shuffled” pass; permutation counts fail.
2. Swap with random j ∈ [0, n−1] every step: the nⁿ-vs-n! bias above. Visually indistinguishable from correct; provably non-uniform for n ≥ 3.
3. Deterministic pivot: taking a[hi] as pivot without the random swap → O(n²) on sorted input; LC 215 includes such tests and Python recursion-based versions also die by stack depth.
4. k-th largest index arithmetic: k-th largest = index n−k (0-indexed) k-th smallest; off-by-one here returns the (k+1)-th. Assert on ([3,2,1,5,6,4], 2) → 5 before submitting.
5. Reservoir drawing j on [0, i−1]: the i-th item then survives with k/i, not k/(i+1) — early items get overweighted. The inclusive bound carries the proof.
6. rand10 truncating instead of rejecting: rand49 % 10 + 1 gives 1..9 five preimages and 10 four — a 25% relative bias no unit test with n=1000 will catch; only bucket-count tests at ~10⁵ trials expose it.

Debugging Strategy

Bias bugs don’t crash — they skew. So test distributions, not runs: bucket-count every randomized routine at ≥ 10⁵ trials and compare against expectation with a ±4σ band (σ = √(Np(1−p))); a correct implementation almost never trips it, and Sattolo/truncation bugs trip it instantly (identity permutation count = 0 is the smoking gun for bug 1). For quickselect, fix random.seed(...) to make failures reproducible, then print (lo, hi, i, k) per iteration — the window must strictly shrink and always contain k. For rand10, histogram the pre-rejection v: it must be flat on 1..49 with everything above 40 discarded.

Mastery Criteria

• Quickselect (iterative, random pivot) from blank, passing duplicates tests, in <10 minutes.
• Fisher–Yates + uniformity proof by induction delivered in <3 minutes without notes.
• Reservoir sampling written and the k/(i+1) induction stated in <8 minutes (LC 382 + LC 398 both cold).
• rand10 with the 2.45-expected-calls derivation in <6 minutes; recycled-entropy variant described.
• Named which of the four is Las Vegas vs Monte Carlo and defended expected-vs-worst-case under pushback.
• Explained hash-seed randomization / hash-flooding in <2 minutes, connecting to phase-03 lab-06.