You are reading a massive log file that does not fit in memory. You need to pick 5 random lines where every line has an equal chance of being selected. You do not even know how many lines there are. How would you solve this?

This is the Reservoir Sampling problem, and it is elegant, practical, and a favorite in coding interviews. It combines a simple probability argument with a streaming algorithm that processes data in a single pass. Once you see the proof, it feels almost magical that it works.

Probability shows up in DSA more than most people expect. From shuffling arrays fairly to analyzing the expected runtime of randomized quicksort, a solid grasp of probability fundamentals gives you tools that deterministic thinking alone cannot provide. In this chapter, we will build up from the basics, then dive into two classic algorithms that interviewers love: Reservoir Sampling and Fisher-Yates Shuffle.

Randomized algorithms appear across systems and interviews alike. Understanding probability lets you reason about correctness and performance in ways that feel unintuitive at first but become second nature with practice.

In interviews, you might be asked to:

In production systems, probability drives:

Interview Insight: When an interviewer asks "how would you pick a random element from a stream?", they are testing whether you know Reservoir Sampling. This is one of those problems where knowing the algorithm makes you look brilliant, and not knowing it makes you struggle.

Before we get to the algorithms, let us establish the probability fundamentals you need.

Sample Space and Events

The sample space S is the set of all possible outcomes of an experiment. An event A is a subset of S. The probability of event A is:

P(A) = |A| / |S| (when all outcomes are equally likely)

For example, rolling a fair die has S = {1, 2, 3, 4, 5, 6}. The event "roll an even number" is A = {2, 4, 6}, so P(A) = 3/6 = 1/2.

Addition Rule

For two events A and B:

P(A or B) = P(A) + P(B) - P(A and B)

If A and B are mutually exclusive (they cannot both happen), this simplifies to P(A or B) = P(A) + P(B).

Multiplication Rule

For two events A and B:

**P(A and B) = P(A) * P(B|A)**

where P(B|A) is the probability of B given that A has occurred. If A and B are independent (knowing A does not change B's probability), this simplifies to P(A and B) = P(A) * P(B).

Probability Tree

A probability tree is a useful way to visualize sequential random events. Here is an example for two coin flips:

Each path from root to leaf represents one outcome. The probability of a path is the product of probabilities along its edges. The sum of all leaf probabilities equals 1.

Expected Value and Linearity of Expectation

The expected value E[X] of a random variable X is the weighted average of its possible values:

**E[X] = sum of (value * probability) for each outcome**

For a fair die: E[X] = 1(1/6) + 2(1/6) + 3(1/6) + 4(1/6) + 5(1/6) + 6(1/6) = 3.5

The most powerful property of expected value is linearity of expectation:

E[X + Y] = E[X] + E[Y]

This holds even when X and Y are not independent. This property is remarkably useful in algorithm analysis.

Interview Insight: Linearity of expectation is the key to analyzing randomized quicksort. Each pair of elements is compared at most once, and the expected number of comparisons across all pairs sums to O(n log n). You do not need the pairs to be independent to add their expectations.

Reservoir Sampling

Reservoir Sampling solves the problem we opened with: selecting k items uniformly at random from a stream of unknown size n, using O(k) memory.

The Algorithm (for general k):

Why does it work? We need to show that every item ends up in the reservoir with probability k/n.

For the special case k = 1, the argument is clean. When we see item i, we keep it with probability 1/i. For item i to survive in the reservoir at the end, it must be kept at step i (probability 1/i) and not replaced at steps i+1, i+2, ..., n. The probability of not being replaced at step j is (j-1)/j. So the overall probability is:

P = (1/i) (i/(i+1)) ((i+1)/(i+2)) ... ((n-1)/n) = 1/n

The fractions telescope beautifully, leaving exactly 1/n for every item. This is what makes the algorithm correct.

Fisher-Yates Shuffle

The Fisher-Yates shuffle (also called the Knuth shuffle) generates a uniformly random permutation of an array in O(n) time and O(1) extra space.

The Algorithm:

The key insight is that at each step, we are selecting which element goes into position i from the remaining unchosen elements (positions 0 through i). After n-1 swaps, every permutation is equally likely.

Why is this correct? There are n! possible permutations of n elements. The algorithm makes n choices: the first with n options, the second with n-1 options, and so on. That gives n (n-1) ... * 1 = n! possible execution paths, each equally likely. Since each path produces a distinct permutation, every permutation has probability 1/n!.

Interview Insight: A common follow-up question is "what happens if you pick j from 0 to n-1 at every step instead of 0 to i?" This produces a biased shuffle. For n=3, there are 3^3 = 27 execution paths but only 3! = 6 permutations, and 27 is not divisible by 6. Some permutations will appear more often than others.

Reservoir Sampling (k=1, stream of 5 elements)

Let us trace through Reservoir Sampling with k=1 on the stream [A, B, C, D, E].

Let us verify the probability that each item is selected equals 1/5:

Every item has exactly a 1/5 chance. The telescoping product is what makes this work.

Fisher-Yates Shuffle on [1, 2, 3, 4]

Notice that at each step, the range of j shrinks by one. Position i is "locked in" after step i, meaning only positions 0 through i-1 are still candidates for future swaps. This is what guarantees a uniform distribution.

Reservoir Sampling (k=1)

Java

Python

C++

C#

JavaScript

TypeScript

Reservoir Sampling (General k)

Java

Python

C++

C#

JavaScript

TypeScript

Fisher-Yates Shuffle

Java

Python

C++

C#

JavaScript

TypeScript

Reservoir Sampling

This is optimal. You must read every element at least once (you cannot skip elements in a stream and still guarantee uniformity), so O(n) time is a lower bound. And you need O(k) space to hold the result.

Fisher-Yates Shuffle

Fisher-Yates is also optimal. Generating a random permutation requires touching each element at least once, so O(n) is a lower bound for time.

Why Randomization Helps

Randomized algorithms trade determinism for performance guarantees that hold "in expectation" or "with high probability."

The classic example is randomized quicksort. Deterministic quicksort with a fixed pivot strategy (like always choosing the first element) degrades to O(n^2) on sorted input. Randomized quicksort picks a random pivot, making O(n^2) behavior astronomically unlikely regardless of input. The expected time is O(n log n) for any input.

The randomness makes the algorithm robust against adversarial inputs. No matter what data you feed it, the expected performance is O(n log n). This is a fundamentally different guarantee than "O(n log n) on average-case random input."

1. Biased Shuffle from Wrong Random Range

The most common mistake in implementing Fisher-Yates is picking j from the full range [0, n-1] at every step instead of [0, i].

This produces n^n possible execution paths instead of n!, and since n^n is not divisible by n! for n >= 3, some permutations will be more likely than others. For a 3-element array, this bias is measurable: some permutations appear roughly 33% more often than they should.

2. Off-by-One in Reservoir Sampling

A subtle error is using the wrong range for the random index. If you generate j in [0, i-1] instead of [0, i], or use [1, i] instead of [1, i] inclusive, the probabilities no longer telescope correctly.

With rand.nextInt(i) the range is [0, i-1], giving each new item a slightly higher chance of entering the reservoir than it should have. The final distribution will not be uniform.

3. Using rand() % n for "Uniform" Random Numbers

In C and C++, the expression rand() % n is not truly uniform when RAND_MAX + 1 is not divisible by n. For example, if RAND_MAX is 32767 and n is 3, there are 32768 possible values. Since 32768 = 10922 * 3 + 2, the values 0 and 1 are each slightly more likely (10923/32768) than value 2 (10922/32768).

Use std::uniform_int_distribution in C++ or the language-appropriate uniform random facility. In Java, Random.nextInt(bound) handles this correctly. In Python, random.randint(a, b) is uniform.

4. Forgetting That Reservoir Must Be Filled First

When implementing general-k Reservoir Sampling, you must fill the reservoir with the first k items before starting the replacement logic. A common bug is starting the replacement loop at index 0 instead of index k, which corrupts the initial reservoir state.

Q1: How would you select a random node from a linked list in one pass, without knowing the length?

This is Reservoir Sampling with k=1. Walk through the list, keeping a counter i starting at 1. For each node, generate a random number in [1, i]. If it equals 1, replace the current selection with this node. After reaching the end, the selected node is uniformly random.

The proof is the same telescoping argument. Node i is selected at step i with probability 1/i, and survives all subsequent steps with probability i/(i+1) (i+1)/(i+2) ... * (n-1)/n. The product telescopes to 1/n.

Q2: Why does Fisher-Yates produce a uniform shuffle, but picking a random index from [0, n-1] at every step does not?

Fisher-Yates makes choices that shrink by one each step: n choices, then n-1, then n-2, and so on. This produces n! equally likely execution paths, one for each permutation. The naive approach with a fixed range [0, n-1] produces n^(n-1) execution paths. Since n^(n-1) is generally not divisible by n!, multiple paths map to the same permutation unevenly, creating bias.

For n=3: Fisher-Yates has 3 2 1 = 6 paths for 6 permutations. The naive approach has 3^2 = 9 paths for 6 permutations. 9 is not divisible by 6, so at least one permutation must appear more often.

Q3: Can you modify Reservoir Sampling to give weighted sampling, where item i has weight w_i?

Yes. Instead of replacing the reservoir element with probability 1/i, use weighted replacement. One approach: for each item, generate a random key = rand()^(1/w_i) and keep the k items with the largest keys. This is the algorithm by Efraimidis and Spirakis (2006). The key insight is that raising a uniform random number to the power 1/w gives heavier items larger keys on average, so they are more likely to remain in the reservoir.

Q4: What is the expected number of comparisons in randomized quicksort, and how do you derive it using linearity of expectation?

The expected number of comparisons is 2n ln(n), which is O(n log n). The derivation uses linearity of expectation. For each pair of elements (i, j) in the sorted order, define an indicator variable X_ij that is 1 if i and j are ever compared. Two elements are compared only if one of them is chosen as a pivot before any element between them. The probability of this is 2/(j - i + 1). The expected total comparisons is the sum of 2/(j - i + 1) over all pairs, which evaluates to 2n H_n (where H_n is the n-th harmonic number), approximately 2n * ln(n).