Randomized Algorithms: Reservoir Sampling, Quickselect, and Fisher-Yates

Algorithm/Topic Statement#

Randomized algorithms use random choices internally to achieve simpler designs, faster expected runtimes, or stronger probabilistic guarantees than any deterministic algorithm. The four most-asked randomized algorithms in coding interviews are reservoir sampling for selecting items from a stream of unknown length, quickselect for finding the kth smallest element in expected linear time, Fisher-Yates shuffle for producing a uniformly random permutation, and Bloom filters for probabilistic membership tests. Each one combines a clever invariant with elementary probability to deliver guarantees that look magical at first glance but follow from straightforward induction. These algorithms pop up everywhere in production systems, from sampling logs to load balancing to deduplicating cache hits.

Why This Topic Matters#

Randomized algorithms are the favorite tool of senior systems engineers because they often outperform deterministic alternatives in practice. Reservoir sampling lets you pick a uniform random sample from a Twitter or Kafka stream in constant memory. Quickselect powers nth percentile computation in databases. Fisher-Yates shuffle is the backbone of card games, A/B testing assignment, and stochastic optimization. Bloom filters guard expensive lookups in Cassandra, Bitcoin, and CDN caches. Interviewers love these algorithms because they probe both probability reasoning and algorithmic creativity. A candidate who can prove that reservoir sampling produces a uniform sample demonstrates command of induction, conditional probability, and clean code structure all at once. Beyond interviews, these techniques generalize to sketches, locality-sensitive hashing, and randomized linear algebra used in machine learning.

The Core Insight (math intuition + proof sketch)#

Reservoir sampling works because of a clever telescoping induction. To select k items uniformly from a stream, fill the reservoir with the first k items. For each subsequent item with index i greater than k, include it with probability k divided by i, replacing a uniformly random reservoir slot. The proof that every item ends up with probability k divided by n is by induction on n. After processing the first k items, each is in the reservoir with probability one, which equals k divided by k. Suppose the invariant holds after item n minus one. When item n arrives, it joins the reservoir with probability k divided by n. Each item already in the reservoir survives with probability one minus the chance of being kicked, which is one minus k divided by n times one over k, equal to n minus one over n. Combine with the inductive probability k divided by n minus one to get k divided by n exactly.

Quickselect mirrors quicksort but recurses into only one side. With a random pivot, the partition splits the array into expected halves, and the recurrence T of n equals T of three quarters n plus order n solves to order n in expectation. The worst case is order n squared but a random pivot makes the bad case astronomically unlikely. Fisher-Yates produces a uniformly random permutation by swapping each position with a random earlier or equal position. The proof shows there are exactly n factorial possible swap sequences, each equally likely, mapping bijectively to permutations. Bloom filters trade space for false positive rate using k independent hash functions, with the false positive probability bounded by the formula one minus the quantity one minus one over m raised to k times n, all raised to k, which approaches the optimal value when k equals m divided by n times the natural log of two.

Visual Dry Run / Worked Example#

Walk through reservoir sampling with k equal to 2 and a stream 10, 20, 30, 40, 50. Initially the reservoir holds 10 and 20. Item 30 has index 3, joins with probability two thirds. If it joins, it kicks 10 or 20 uniformly. After processing 30, every one of 10, 20, 30 has probability two thirds of being in the reservoir. Item 40 with index 4 joins with probability two over four, which is one half. Item 50 with index 5 joins with probability two fifths. Final probability for any item is two divided by five, exactly the uniform sample probability.

For quickselect, take the array 7, 2, 1, 6, 8, 5, 3, 4 and find the third smallest element. Random pivot lands on 5. Partition produces left with 2, 1, 3, 4 and right with 7, 6, 8. The pivot index is four. Since k equals three is less than four, recurse into the left side seeking the third smallest there. Random pivot in the left partition lands on 3. Partition gives 2, 1 to the left and 4 to the right. Now k equals three falls past the left subarray of size two and lands on the pivot 3. Return 3.

Solution / Implementation#

Python (reservoir sampling, quickselect, shuffle)#

import random
 
def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir
 
def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    low = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    high = [x for x in arr if x > pivot]
    if k <= len(low):
        return quickselect(low, k)
    if k <= len(low) + len(mid):
        return pivot
    return quickselect(high, k - len(low) - len(mid))
 
def fisher_yates(arr):
    n = len(arr)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

JavaScript#

function reservoirSample(stream, k) {
  const reservoir = [];
  let i = 0;
  for (const item of stream) {
    if (i < k) {
      reservoir.push(item);
    } else {
      const j = Math.floor(Math.random() * (i + 1));
      if (j < k) reservoir[j] = item;
    }
    i++;
  }
  return reservoir;
}
 
function fisherYates(arr) {
  const a = [...arr];
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

Reservoir sampling is order n with order k extra space. Quickselect is expected order n, worst case order n squared. Fisher-Yates is order n with order one extra space. Bloom filter operations are order k for the number of hash functions per add or query.

Common Mistakes#

The most common reservoir sampling bug is using random integer between zero and k minus one instead of zero and i, which breaks uniformity. Always include the new item's index in the random range. Quickselect bugs often come from in-place partitioning when the pivot index is not tracked correctly. Use the simple list comprehension version in Python or the Lomuto partition in C-like languages until you are comfortable with Hoare. Fisher-Yates suffers a notorious off-by-one if you swap with random of zero to n minus one for every position; that produces a biased shuffle. The correct loop swaps position i with a random position in zero to i inclusive, decreasing i. Bloom filters fail catastrophically if your hash functions are correlated; use distinct seeds or distinct hash families. Finally, do not forget that randomized algorithms still require correctness arguments. Saying the algorithm is randomized is not a proof.

Interview Tips#

When the problem asks about a stream with unknown length, start with reservoir sampling. When the problem asks for the kth element in unsorted data, start with quickselect, mention the worst case, and propose a deterministic median-of-medians fallback if the interviewer probes. When asked to shuffle, narrate Fisher-Yates and explain why the naive sort by random key approach gives biased results. For probabilistic data structures, name Bloom filters, Count-Min sketches, and HyperLogLog and explain when each is appropriate. Always state the expected time, the probability of failure, and the resource tradeoffs out loud.

Follow-up Questions#

Could you derive the closed-form expected runtime of quickselect with random pivots from the recurrence? How would you implement a weighted reservoir sampling variant where each item has a weight? What are the practical hash function choices for Bloom filters, and why does the textbook k equal to m over n times log two minimize the false positive rate? Can you describe Count-Min sketch and explain when it is preferable to a Bloom filter?

Key Takeaways#

• Reservoir sampling selects k items uniformly from a stream of unknown length using order one extra memory beyond the reservoir.
• Quickselect finds the kth smallest in expected linear time using random pivots and one-sided recursion.
• Fisher-Yates shuffle produces a uniformly random permutation in linear time using only swaps with earlier positions.
• Bloom filters trade probabilistic correctness for compact space and constant time membership tests.
• Random pivots and uniform indices are the heart of correctness; off-by-one bugs silently break uniformity.
• These randomized algorithms power production systems at every major tech company and appear constantly in interviews.