Randomised algorithms ladder: shuffle, sample, reject

In this article

1. Before you start
2. Why interviewers ask this
3. Randomised algorithms from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one rung of the coding interview patterns path.

Why interviewers ask this

A random answer is easy to write and easy to get quietly wrong, so interviewers use it to see whether a candidate can prove the odds instead of only running the code. Candidates report a Fisher-Yates shuffle variant with a time derivation and a probability question in a machine learning engineer screen at Uber, a request to return a random index among tied maxima at Meta, a rejection-sampling problem close to rand7 to rand10 in a coding round at LinkedIn, add, remove and sample on a dictionary at Google DeepMind, and a weighted insert, delete and get-random design at Hudson River Trading. These are reported by candidates, not confirmed by the companies.

A weak answer calls the code "random enough". A strong answer states what is random, says whether the answer or the running time varies, and proves each outcome has the intended probability. That proof is short for every rung below.

Randomised algorithms from first principles

Randomised algorithm

A randomised algorithm is an algorithm that, while it runs, tosses coins and makes decisions from the outcomes, so its behaviour depends on chance as well as on its input. Programs use randomised algorithms to get fair choices, fast average running times and answers over data too large to keep.

Las Vegas algorithm

A Las Vegas algorithm is a randomised algorithm that always returns a correct answer but whose running time is a random variable, so its time bounds hold only in expectation.

Monte Carlo algorithm

A Monte Carlo algorithm is a randomised algorithm with a fixed running time whose answer may be wrong, so its correctness is left to chance and is stated as a probability.

Reservoir sampling

Reservoir sampling is a one-pass method that keeps a uniform random sample of fixed size from a stream whose length is unknown, by deciding for each arriving item whether it replaces a held item.

In plain words

Think of a raffle drum. You reach in without looking, and every ticket has the same chance. The ladder asks how to get that fairness from a program.

The analogy breaks at one point. A computer has no drum. A pseudorandom number generator (PRNG) is a program that turns a starting value into numbers that look random. Real implementations use one, and the textbook proofs assume ideal random bits, so actual behaviour can deviate (Wikipedia, randomised algorithm).

In one precise sentence, every rung below picks items with known probabilities and then proves them. Each rung asks the same two questions. What is random? What do I get to be sure of?

Step 1: Las Vegas and Monte Carlo say what is random

Las Vegas and Monte Carlo split randomised algorithms by what chance is allowed to touch. The Duke University course 532 notes say a Monte Carlo algorithm may fail or return incorrect answers but has a runtime independent of the randomness. A Las Vegas algorithm always returns the correct answer, but its runtime bounds hold only in expectation. The Harvard course 125 notes put it the same way: a Las Vegas algorithm is always correct, but its running time is a random variable.

Las Vegas always returns a correct answer and its running time is random. A standard example finds an 'a' in an array where half the entries are 'a': pick a random position until it holds an 'a'. Each pick succeeds with probability one half, so the expected number of picks is two.¹ The count has no fixed upper limit, yet the answer is never wrong.

You now know the two questions to ask of any random code: is the answer random, or only the time?

Step 2: Fisher-Yates shuffles in place, and one index bug breaks it

The Fisher-Yates shuffle is an algorithm that puts a list in uniformly random order in one pass by swapping each position with a randomly chosen position that is still undecided. Durstenfeld introduced the modern in-place version in 1964, and every permutation is equally likely.

import random

def shuffle(a):
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)   # whole undecided range, including i itself
        a[i], a[j] = a[j], a[i]

Position by position the choices shrink: the last position picks among n items, the next among one fewer, and so on. MathWorld notes every permutation corresponds to exactly one sequence of choices, so each has probability 1/n!. Fisher-Yates runs in linear time with constant extra space, given constant-time random indexes.

The bug that looks right swaps each position with any index in the whole list. For three items that makes 27 paths, and six orderings cannot share 27 paths equally: three orderings are reached four times and three are reached five times.¹

Step 3: Reservoir sampling picks fairly from a stream

Reservoir sampling keeps a fair sample from a stream without knowing how long the stream is. Start with a reservoir of one item. Keep the first item. When item number i arrives, replace the held item with probability 1/i. This basic version, known as Algorithm R, uses that standard update rule, and the reservoir sampling page proves by induction that after each step the reservoir holds a uniform sample.

The proof for one slot is a product. Item one survives to the end of a five-item stream with probability one times one half times two thirds times three quarters times four fifths, which is one fifth, and every later item also ends at one fifth.¹ Larger reservoirs give each item a probability of k divided by n.

Algorithm R generates one random number per input item, so its time is linear, and its memory grows with the sample size. It does not need n in advance, which is its whole point.

Step 4: Rejection sampling retries until the candidate fits

In its simplest form, rejection sampling is a method that draws candidates from an easy distribution and discards those outside the target set, so the kept ones are uniform over the target. The general method accepts a candidate with probability proportional to the target density divided by the proposal density. It is a Las Vegas algorithm: the answer is exact but the number of retries is random.

The classic question builds a uniform number from one to ten out of a function that returns one to seven uniformly. Call it twice and form a grid index from one to 49. Keep the first 40 cells and map them onto ten outputs, four cells each; retry on the other nine.¹

def rand10():
    while True:
        idx = (rand7() - 1) * 7 + rand7()   # 1..49, each equally likely
        if idx <= 40:
            return (idx - 1) % 10 + 1

The acceptance probability is 40/49, so the expected number of pairs is 49/40.¹

1 · What is random2 · Shuffle3 · Stream4 · RetryReplay

Step-by-step description

1. Las Vegas: random time. Monte Carlo: random answer.
2. Fisher-Yates orders a list in one pass.
3. Reservoir sampling needs no length.
4. Rejection sampling keeps only what fits.

• Las Vegas always returns a correct answer and its running time is random.
• Fisher-Yates runs in linear time with constant extra space.
• Reservoir sampling keeps a uniform sample of a stream of unknown length.
• Rejection sampling retries until a candidate fits, so its running time is random.

Worked example

The tied-maximum question asks for the index of the largest number in a list, picking one at random if several tie. Take the illustrative list 3, 7, 7, 2, 7, 5. The maximum is 7, held at zero-based indices 1, 2 and 4, so there are three ties.¹

The single-pass solution is reservoir sampling over ties only:

import random

def random_argmax(a):
    best, pick, ties = None, -1, 0
    for i, x in enumerate(a):
        if best is None or x > best:
            best, pick, ties = x, i, 1
        elif x == best:
            ties += 1
            if random.randrange(ties) == 0:   # probability 1/ties
                pick = i
    return pick

On the first tie the index is kept. On the second tie it is replaced with probability 1/2, on the third with probability 1/3. Index 1 survives with 1/2 times 2/3, index 2 with 1/2 times 2/3, and index 4 is chosen with 1/3, so each is 1/3.¹ A new strictly larger value resets the tie count, which is the line candidates forget.

The chart below shows why the naive shuffle fails: every bar should be 4.5 for a uniform result.¹

Text description of the diagram

• A naive shuffle of three items has 27 paths, which six orderings cannot share equally.
• Three orderings are reached 4 times and three are reached 5 times.

Trade-offs and edge cases

Each rung buys fairness at a cost. Fisher-Yates runs in linear time with constant extra space (MathWorld). Reservoir sampling memory grows with the sample size. Rejection sampling needs an expected, not fixed, number of retries.

Text description of the diagram

• Fisher-Yates runs in linear time with constant extra space.
• Reservoir sampling memory grows with the sample size.
• Rejection sampling needs an expected, not fixed, number of retries.

Adding, removing and sampling from a dictionary in constant time needs a list of keys beside the dictionary. This short class keeps a pos dictionary (key to list index) and a keys list:

import random

class SampleDict:
    def __init__(self):
        self.pos = {}    # key -> index in self.keys
        self.keys = []

    def insert(self, key):
        if key in self.pos:
            return
        self.pos[key] = len(self.keys)
        self.keys.append(key)

    def remove(self, key):
        i = self.pos.pop(key)
        last = self.keys.pop()
        if i < len(self.keys):        # the removed key was not the last one
            self.keys[i] = last       # move the last key into the freed slot
            self.pos[last] = i

    def get_random(self):
        return random.choice(self.keys)

The Python pitfall: random.choice(d) on a dictionary does not sample its keys. It indexes the dictionary by an integer and usually raises KeyError, so the sample must come from a list.¹

Edge cases that change the answer:

• Random keys and a sort. Shuffling by sorting on random keys works but costs more than linear time, where Fisher-Yates stays linear. Duplicate random keys also bias the result unless the keys are wide enough or ties are re-drawn.
• Collect instead of stream. For ties, gathering every tied index and choosing one is simple but needs memory for all of them; the single pass uses constant memory.
• Dictionary sampling. Choosing from a list built from the dictionary's keys costs linear time per call. A common design keeps a list of keys plus a dictionary from key to list position, so insert, delete and random pick are all constant time; delete swaps the last key into the gap. The Python interview questions page and the defaultdict guide cover the dictionary side, and hash-map lookups by prefix sum show another use of a dictionary of positions.
• Randomised pivots. Quickselect with a random pivot is Las Vegas style: the answer is always right, the time varies. See k closest points to origin.
• The generator. The proofs assume ideal random bits; real code uses a PRNG (Wikipedia).

How to answer it in an interview

The spoken structure: say the plan, say the update rule, prove the probability in one line, then give time, memory and the simpler alternative.

Common mistakes

• "I swap each position with a random index from the whole list." (wrong) That makes more paths than orderings and cannot be uniform. (right) "I pick only from the undecided range, including the current position."
• "Randomised means the answer might be wrong." (wrong) Only Monte Carlo algorithms may be wrong. (right) "A Las Vegas algorithm is always correct; its time varies."
• "Reservoir sampling needs the length first." (wrong) It is built for streams of unknown size. (right) "Item i replaces the held item with probability one over i."
• "On a new maximum I keep counting ties." (wrong) Old ties belong to a smaller value. (right) "I reset the count to one."

Follow-up questions

How do you return the index of the largest number, picking randomly among ties?

Scan once and apply reservoir sampling to the tied positions only, resetting on a new maximum. The alternative is to collect all tied indices and choose one, which costs memory proportional to the number of ties.

How do you add, remove and sample elements in a dictionary?

Adding and removing are direct dictionary operations. For constant-time sampling, keep a list of keys and a dictionary from key to its list position, and on removal swap the last key into the freed slot.

What is the difference between a Las Vegas and a Monte Carlo algorithm?

A Las Vegas algorithm always returns the correct answer and its running time is random. A Monte Carlo algorithm has a fixed running time and its correctness is probabilistic (Harvard course 125 notes).

Does reservoir sampling need to know the stream length?

No. The rule "replace with probability one over i" uses only the position of the current item, so the length can be unknown and the sample stays uniform at every step.

How would you sample with weights?

Build cumulative weights and binary-search a random number against them. For updates between samples, a Fenwick tree is a standard choice, and the alias method gives constant-time samples when weights are fixed.

Is computer randomness truly random?

Standard-library generators are pseudorandom, and the textbook proofs assume ideal random bits, so behaviour can deviate from the theory. Security code uses a cryptographically secure generator instead.

Sources

1. Lecture 10 scribe notes: Las Vegas and Monte Carlo algorithms — Duke University, COMPSCI 532, Fall 2015, 30 Sep 2015
2. Computer Science 125 (CS125) Lecture 18: Randomized Algorithms — Harvard SEAS, CS125, Fall 2016, 1 Sep 2016
3. Randomized algorithm — Wikipedia, 26 Oct 2026
4. Fisher-Yates shuffle — Wikipedia, 26 Oct 2026
5. Fisher-Yates Shuffle — Wolfram MathWorld, 26 Oct 2026
6. Reservoir sampling — Wikipedia, 26 Oct 2026