Randomization and sampling

What "random" has to mean before you can code it

Most interview problems that say "random" are not about the generator. They hand you one source of randomness (Math.random(), a rand7(), a fair coin) and ask you to build a different distribution out of it: a shuffle, one item from a stream, an index chosen in proportion to weights, a point in a circle. What the grader checks is a statement about probability. Each outcome must have exactly the chance the problem promises, usually "all outcomes equally likely", and a later result must not depend on an earlier one. That is why a solution can pass every example and still be wrong: one run of a random function never shows whether its probabilities are right.

Three habits carry the whole chapter, and each technique below repeats them.

• State the target as one sentence. "Each of the n! orders has probability 1/n!." "Each of the n items seen so far is held with probability 1/n."
• Argue that the algorithm reaches it. Either a counting argument (how many equally likely random choices are there, and how do they map onto outcomes?) or an induction on the number of items.
• Check it with an experiment you can repeat. That needs a generator you control, counts over many trials, and a number to compare them with. A random function you cannot replay is a function you cannot debug.

The techniques are few. Fisher-Yates builds a uniform shuffle. Reservoir sampling picks from a stream whose length you do not know. Prefix sums with a binary search turn weights into probabilities. Rejection sampling builds one distribution out of another by throwing away the draws that do not fit. Randomized quickselect uses a random pivot to get an expected linear running time. The last sections cover hashing as an alternative to random choice and how to answer "is this random enough?" out loud.

Math.random and its limits

Math.random() returns a number x with 0 <= x < 1: it can be 0 and is never 1. The language only asks that the values be approximately uniform. It does not say which algorithm produces them, and there is no way to give it a seed, so two runs of the same program see different numbers. The interview building block is the integer in 0 .. n - 1: scale by n and drop the fraction. The helpers below take the generator as an argument, rng, a function that returns a number in [0, 1). In production code you pass Math.random. In tests you pass something you can replay, as the next sections show.

function randInt(rng, n) {
  return Math.floor(rng() * n); // 0 .. n - 1, each equally likely
}

function randBetween(rng, lo, hi) {
  return lo + randInt(rng, hi - lo + 1); // lo .. hi, both ends included
}

Two recipes that look equivalent are not. Math.round(x * (n - 1)) gives the values 0 and n - 1 only half the width of the others: round returns 0 for [0, 0.5) but 1 for [0.5, 1.5), a full unit. For six values the ends have probability 0.5/5 = 10% each and the middle four 20% each. And (x * n) | 0 truncates the result to a 32-bit signed integer, so for n of 2³¹ or more it can go negative: (0.9999 * 2 ** 32) | 0 is -429497. Use Math.floor.

Why Math.random is the wrong tool for anything secret

Math.random is not cryptographically secure: nothing promises that someone who has seen some of its outputs cannot predict the next ones. A session token, a password, a lottery draw or a shuffle that decides who wins money needs the platform's secure source: crypto.getRandomValues in browsers and in Node, or crypto.randomInt from node:crypto, which returns a uniform integer in a range. In an interview one sentence is enough: "Math.random is fine for a simulation or a game, not for anything an attacker would want to guess."

Modulo bias: why x % n is not a uniform pick

The other common way to shrink a random integer into 0 .. n - 1 is the remainder. Suppose a source gives M equally likely raw values 0 .. M - 1. The remainder x % n is uniform only when n divides M. Otherwise the first M % n remainders have one more raw value mapped onto them than the rest.

function residueCounts(values, n) {
  const counts = new Array(n).fill(0);
  for (let x = 0; x < values; x++) counts[x % n]++; // x stands for one equally likely raw output
  return counts;
}

The bias shrinks as the raw range grows far beyond n, which is why it hides in real code and shows up in small examples. The fix is not to patch the remainder. It is to refuse the raw values that fall in the incomplete last group and draw again. That is rejection sampling, and it has its own section below. The same finite-grid argument applies to Math.floor(x * n): any generator has finitely many outputs, 2^b of them for a b-bit generator, so the number of raw values behind two different results differs by at most one, out of about 2^b/n each. For the sizes in interviews that is far below anything you could measure, so the standard answer is to state the assumption ("I assume Math.random is uniform on [0, 1)") and move on.

The counting test: can this algorithm be uniform at all?

Before proving that a random algorithm is right, ask whether it can be. Most of the algorithms in this chapter make a fixed number of independent random choices, and the combination of choices decides the result. If there are N equally likely combinations in total and each one produces exactly one result, then every result gets a probability that is a whole number divided by N. For M results to be equally likely, each must receive exactly N / M combinations, so M must divide N. That is a one-line check that rules out a lot of tempting code.

The third row is the real lesson of rand10. Because no algorithm with a fixed cap on its rand7 calls can work, the solution must be allowed to loop: draw, and if the draw is unusable, draw again. Rejection sampling is not a trick. It is forced. When the count says "possible", you still owe the argument that the combinations land evenly. When it says "impossible", you are done, and you can say so in one sentence.

Testing randomized code: inject the generator, seed it, count

A function that calls Math.random() inside cannot be tested well. You cannot replay a failure, and a test that checks a distribution fails on some runs for no reason you can find. The cure is to make the randomness a parameter. Every algorithm in this chapter takes the generator as an argument, and the exercises do the same. That allows three kinds of test.

• A scripted generator returns values you list in advance. The program's path is then fixed, so you can trace it by hand and assert an exact answer. All the dry-run tables below use one.
• A seeded generator produces a long but repeatable sequence. Run the function a hundred thousand times, count the outcomes, and compare the counts with the probabilities you claim. The test gives the same verdict every time.
• Property checks do not look at the distribution at all. The shuffled array is a permutation of the input, the sample has k distinct members, the input was not changed.

function mulberry32(seed) {
  let a = seed >>> 0;
  return function () {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; // always in [0, 1)
  };
}

function scripted(values) {
  let next = 0;
  return function () {
    if (next >= values.length) throw new Error("the script ran out of values");
    return values[next++];
  };
}

function tally(trials, keys, run) {
  const counts = new Map(keys.map((key) => [key, 0])); // every possible outcome starts at 0
  for (let t = 0; t < trials; t++) {
    const key = run();
    if (!counts.has(key)) throw new Error("impossible outcome: " + key);
    counts.set(key, counts.get(key) + 1);
  }
  return keys.map((key) => counts.get(key));
}

function chiSquare(observed) {
  const total = observed.reduce((sum, count) => sum + count, 0);
  const expected = total / observed.length;
  let statistic = 0;
  for (const count of observed) statistic += (count - expected) ** 2 / expected;
  return statistic;
}

mulberry32 is a small 32-bit generator that is easy to paste and is good enough for tests. It is not secure and you are not expected to recite its constants. If an interviewer asks you to write a seedable generator, three lines of a linear congruential generator are enough:

function lcg(seed) {
  let state = seed >>> 0;
  return function () {
    state = (state * 1664525 + 1013904223) % 4294967296; // exact: the product stays below 2 ** 53
    return state / 4294967296;
  };
}

A linear congruential generator has weak low-order bits, which is why this version divides by 2³² and uses the high-order part of the state (the way randInt does) rather than taking state % n. For a test, either generator is fine. Never use either for secrets.

Reading a chi-square number

Counts from a random experiment never match the expected counts exactly, so you need a rule for "close enough". The chi-square statistic adds up, over all outcomes, the squared gap between observed and expected count divided by the expected count. For a statistic computed from k outcomes, compare it with the critical value for k - 1 degrees of freedom. If the algorithm really is uniform, the statistic exceeds the 0.1% critical value in about one run out of a thousand.

Dry run: 60,000 rolls of a six-sided die, seed 1

The call is tally(60000, [0, 1, 2, 3, 4, 5], () => randInt(rng, 6)) with rng = mulberry32(1). The expected count for each face is 60,000 / 6 = 10,000.

3.99 is below the critical value 20.52 for 5 degrees of freedom, so the die looks fair. For contrast, the same seed with Math.round(rng() * 5) gives the counts 6009, 11985, 11958, 12208, 11908 and 5932, and a statistic of about 4,877: the end values come out at about half the others, as the width argument predicted.

Fisher-Yates and the proof that every order is equally likely

The task: rearrange an array so that each of its n! orders has probability 1/n!. The natural plan is to fill the positions one at a time, choosing uniformly among the elements not yet placed. Choosing the element for the last position first leaves a smaller array of the same problem, and the chosen element can be moved into place by swapping it with the position being filled. Everything not yet placed then stays packed in a prefix of the array, so no extra storage is needed.

function shuffle(items, rng) {
  const a = items.slice(); // work on a copy
  for (let i = a.length - 1; i > 0; i--) {
    const j = randInt(rng, i + 1); // 0 .. i, so position i may keep its own element
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function naiveShuffle(items, rng) {
  const a = items.slice();
  for (let i = 0; i < a.length; i++) {
    const j = randInt(rng, a.length); // the bug: every step draws from the whole array
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function sortShuffle(items, rng) {
  return items.slice().sort(() => rng() - 0.5); // the popular one-liner, with the generator passed in
}

function shuffleByKeys(items, rng) {
  return items
    .map((item) => ({ item, key: rng() }))
    .sort((p, q) => p.key - q.key)
    .map((pair) => pair.item);
}

function sampleDistinct(items, k, rng) {
  const a = items.slice();
  const count = Math.min(k, a.length);
  for (let i = 0; i < count; i++) {
    const j = i + randInt(rng, a.length - i); // a random element from the part not yet chosen
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a.slice(0, count);
}

Read shuffle first. sampleDistinct is the same loop run from the front for only k steps, so it returns k elements chosen without replacement in a uniformly random order. naiveShuffle, sortShuffle and shuffleByKeys are the other ways people try, and are measured in the next section.

Dry run: shuffle(["A", "B", "C", "D"]) with the script 0.6, 0.9, 0.3

The result is ["B", "A", "D", "C"]. Position 0 is never drawn for: when i reaches 0 only one element is left, so there is nothing to choose, which is why the loop stops at i > 0. The middle row swapped a position with itself. That is not wasted. It is the case where the element already there is the one chosen, and leaving it out would make that outcome impossible.

Why every order has probability exactly 1/n!

Write the random choices as a sequence (jn-1, ..., j1), where ji is drawn from 0 .. i. The choices are independent, so each of the n * (n - 1) * ... * 2 = n! sequences has probability 1/n!. Now show that two different sequences always produce different arrays. Given the final array, you can recover the sequence from the back. The element in the last position was put there by the first step and never moved again, so jn-1 is the index that element had in the original array. After undoing that swap, the element in position n - 2 was placed by the second step, and jn-2 is its index in the array as it stood after the first step, and so on down to position 1. Every step is determined, so the map from sequences to arrays never maps two sequences to one array. There are n! sequences and n! possible arrays, so the map is a one-to-one correspondence: each array comes from exactly one sequence, with probability 1/n!. I also checked this by brute force. For every n from 1 to 6, running shuffle on all n! scripted choice sequences produced n! different arrays.

The same fact in the language of an invariant: before the step for position i, the elements in positions 0 .. i are the ones not yet placed, and every one of them is equally likely to be chosen for position i. The step picks one with probability 1/(i + 1) and sets it aside for good, so the chosen order is built one uniform choice at a time.

Why the naive version fails

naiveShuffle swaps each position with a position drawn from the whole array. Its choices form nⁿ equally likely sequences, and by the counting test nⁿ cannot be shared evenly among n! orders. For three items I enumerated all 27 sequences: three orders (123, 312 and 321) come from 4 sequences each, and the other three from 5. The probabilities are 4/27 = 14.8% and 5/27 = 18.5%, instead of 16.7% for all. The measured counts in the next section agree.

Complexity and variations

Fisher-Yates does n - 1 random draws and n - 1 swaps: O(n) time. A copy costs O(n) extra space, and shuffling the caller's array in place costs O(1). Decide which you promise, and say so. sampleDistinct finishes after k steps, so after the O(n) copy it costs O(k): it is the right tool for "k distinct random elements of an array". Starting at the front with j = i + randInt(rng, n - i) is as correct as starting at the back: it is the same argument read from the other end.

Why sort(() => Math.random() - 0.5) is biased: measured

The one-line shuffle appears in many tutorials. It passes a comparator that answers "negative" or "positive" at random, hoping the sort will scramble the array. A comparator is supposed to be consistent: if it says a goes before b now, it must say so next time. This one answers the same question differently each time, and the specification then leaves the resulting order up to the implementation. So the outcome depends on which sorting algorithm the engine uses, and there is a counting proof that no comparison sort can make it fair. Suppose the sort makes at most m comparisons and each answer is an exactly fair coin flip (the real comparator is no better than that). Then every order has probability k/2^m for some whole number k. The target 1/n! is of that form only if n! divides a power of two, and n! has the factor 3 once n is 3 or more. The bias is not a rounding accident. It cannot be avoided.

The next table shows how large it is. Each row runs the method on [1, 2, 3] 60,000 times with mulberry32(7), so a fair method puts about 10,000 in every column. The chi-square line uses 5 degrees of freedom, where the 0.1% critical value is 20.52.

With the comparator, the original order 123 survives 37.5% of the time and 321 31.3%, against 16.7% for a fair shuffle. On four items (24 orders, 120,000 trials, mulberry32(11), 23 degrees of freedom and a critical value of 49.73) the statistics were 31.1 for Fisher-Yates, 3,694.7 for the naive swaps, 139,336.9 for the comparator and 25.5 for random keys. On ten items, element 0 ended in the first position 19.4% of the time with the comparator (100,000 trials, seed 5), against 10.0% with Fisher-Yates. These are measurements of Node 24's sort. Another engine or version sorts differently and would give other numbers, but the counting proof says it cannot give fair ones. A different seed changes every count in the table without changing the verdicts.

shuffleByKeys, the last row, is correct: give every element an independent random key and sort by the key. If all keys are different, each of the n! orders of the keys is equally likely, so each order of the elements is too. Its flaw is cost, O(n log n) against O(n), and ties: two equal keys leave the sort to decide, which is a slight bias when the keys are coarse. Prefer Fisher-Yates and mention random keys only as a correct alternative.

Reservoir sampling: one item from a stream of unknown length

The problem: items arrive one at a time, you cannot go back, you do not know in advance how many will come, and when the stream ends you must return one item chosen uniformly. The obvious plan, store everything and then pick items[randInt(rng, items.length)], uses O(n) memory and fails outright when the stream is too large to hold. The other obvious plan, count the items in one pass and pick an index in a second, needs a stream you can read twice.

Derive the answer by asking what a one-slot memory can do. Keep one candidate. When the first item arrives it must be the candidate, because with one item seen it is the only possible answer. After two items each must be the answer with probability 1/2. The first is already the candidate, so the second must take over with probability 1/2. After three items each needs probability 1/3, so the third takes over with probability 1/3, and so on. In general the i-th item replaces the candidate with probability 1/i.

function sampleOne(stream, rng) {
  let chosen;
  let seen = 0;
  for (const item of stream) {
    seen++;
    if (randInt(rng, seen) === 0) chosen = item; // probability 1 / seen
  }
  return chosen; // undefined for an empty stream
}

function reservoirSample(stream, k, rng) {
  const reservoir = [];
  let seen = 0;
  for (const item of stream) {
    seen++;
    if (reservoir.length < k) {
      reservoir.push(item);
    } else {
      const slot = randInt(rng, seen); // 0 .. seen - 1
      if (slot < k) reservoir[slot] = item; // probability k / seen, and it lands in a uniform slot
    }
  }
  return reservoir;
}

class RandomPickIndex {
  constructor(nums, rng) {
    this.nums = nums;
    this.rng = rng;
  }

  pick(target) {
    let chosen = -1;
    let matches = 0;
    for (let i = 0; i < this.nums.length; i++) {
      if (this.nums[i] !== target) continue;
      matches++;
      if (randInt(this.rng, matches) === 0) chosen = i;
    }
    return chosen;
  }
}

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

class RandomListNode {
  constructor(head, rng) {
    this.head = head;
    this.rng = rng;
  }

  getRandom() {
    let chosen = this.head.val;
    let seen = 0;
    for (let node = this.head; node !== null; node = node.next) {
      seen++;
      if (randInt(this.rng, seen) === 0) chosen = node.val;
    }
    return chosen;
  }
}

function mergeSamples(first, second, rng) {
  const seen = first.seen + second.seen;
  const winner = randInt(rng, seen) < first.seen ? first : second; // each side in proportion to the items it saw
  return { item: winner.item, seen };
}

Notice sampleOne draws a number even for the first item, where randInt(rng, 1) is always 0. That keeps the loop uniform and the script of a test simple: one draw per item.

Dry run: sampleOne over A, B, C, D with the script 0.3, 0.7, 0.2, 0.6

The answer is C. The code replaces exactly when the drawn number is 0, which has probability 1/seen for randInt(rng, seen).

Proof by induction: after i items, each is held with probability exactly 1/i

Base. After one item, the candidate is that item, with probability 1 = 1/1. Step. Assume that after i items each of them is the candidate with probability 1/i. The next item replaces the candidate with probability 1/(i + 1), so the new item itself is held with probability 1/(i + 1), as required. An old item is held after the step only if it was held before and the new item did not replace it. Those two events are independent, because the new draw does not look at the old ones, so the probability is (1/i) * (1 - 1/(i + 1)) = (1/i) * (i/(i + 1)) = 1/(i + 1). Every item, old or new, has probability 1/(i + 1). The induction is complete.

The product telescopes: each numerator cancels the next denominator. I also checked the code two ways. Enumerating all 1 * 2 * 3 * 4 * 5 = 120 scripted draw sequences for five items put each item last standing in exactly 24 of them. And 50,000 seeded runs (mulberry32(3)) on a five-item array gave the counts 10110, 10042, 9876, 9872, 10100, a statistic of 5.56 against a critical value of 18.47.

Cost: one pass, O(n) time, O(1) extra space, and it works on any iterable, including a generator that you can only walk once.

Random pick index and linked list random node

Two classic problems are reservoir sampling in disguise. In random pick index, an array has duplicates, and pick(target) must return a uniformly random index among those holding the target. The easy solution is a map from value to the list of its indices, which makes a pick O(1) but costs O(n) memory. If the array is huge and memory is the constraint, scan it and run reservoir sampling over the matching positions only. That is RandomPickIndex above: matches is the count of candidates so far, and the current match replaces the chosen one with probability 1 / matches.

In linked list random node, you hold only the head, and the length is not known. You could walk the list once to count it and again to stop at a random position, which is two passes. Reservoir sampling does it in one pass with O(1) space, which is the point of the follow-up question in the problem. RandomListNode is the same loop with node = node.next in place of the array index.

Dry run: pick(3) on [1, 3, 2, 3, 3] with the script 0.4, 0.9, 0.1

The pick is index 4. Non-matching values never touch the generator, so the script has one value per match, not per element. A target that is not present returns -1 here, so check what the problem promises. In 30,000 seeded picks (mulberry32(5)) the three matching indices came out 10048, 10051 and 9901 times. On a five-node list, 50,000 calls gave 10051, 9946, 9989, 10071 and 9943, a statistic of 1.39.

Reservoir sampling for k items

Now keep k items instead of one, with every k-element subset of the stream equally likely. The same idea scales. Fill the reservoir with the first k items, since with only k items seen they must all be in it. The i-th item after that (counting from 1, so i is greater than k) should end up in the sample with probability k/i. Draw a number slot from 0 .. i - 1. If slot < k, which has probability k/i, the new item enters and replaces whatever is in that slot. Because the slot is uniform among k, each current member is equally likely to be the one evicted. That is reservoirSample above.

Dry run: reservoirSample(A..E, 2) with the script 0.5, 0.9, 0.1

Proof: each k-subset is equally likely

Claim: after i items, the reservoir, read as a set, is equally likely to be any of the C(i, k) subsets of the items seen. For i = k there is one subset, with probability 1. Assume it for i and take a k-subset S of the first i + 1 items. There are two cases.

• S does not contain item i + 1. The reservoir must have been S already, with probability 1/C(i, k), and the new item must have been skipped, with probability 1 - k/(i + 1) = (i + 1 - k)/(i + 1). The product is (i + 1 - k) / ((i + 1) * C(i, k)).
• S contains item i + 1. Then S minus that item is a (k - 1)-subset of the first i, and the reservoir before the step was that subset plus one other item x. There are i - (k - 1) = i + 1 - k choices for x, each with probability 1/C(i, k). The new item must enter, with probability k/(i + 1), and pick exactly the slot holding x, with probability 1/k. The total is (i + 1 - k) * (1/C(i, k)) * (k/(i + 1)) * (1/k), which is again (i + 1 - k) / ((i + 1) * C(i, k)).

Both cases give the same number, and since C(i + 1, k) = C(i, k) * (i + 1) / (i + 1 - k), that number is 1/C(i + 1, k). Every subset has the same probability. In particular each single item is in the reservoir with probability k/i.

Checks I ran: enumerating every scripted draw sequence, the 10 subsets of a five-item stream with k = 2 each came from exactly 6 of the 60 sequences, and the same held for n = 6, k = 3 (20 subsets, 6 each), n = 7, k = 3 (35 subsets, 24 each) and n = 7, k = 4 (35 subsets, 6 each). With 100,000 seeded runs (mulberry32(4)) on five items with k = 2 the ten subset counts ranged from 9,896 to 10,134 with a statistic of 7.10 against 27.88. With k = 3 on seven items and 350,000 runs the statistic was 26.99 for 34 degrees of freedom (critical value 65.25).

Cost: O(n) time, O(k) space, one pass. The guarantee is about the set of items. The order of the items inside the reservoir array is not promised to be a uniform shuffle, so shuffle the result if the problem needs random order. For k of at least n the loop simply keeps everything.

Merging samples from two streams

If two machines each hold one sampled item together with the number of items they saw, mergeSamples combines them for k = 1: take the first machine's item with probability first.seen / (first.seen + second.seen). Every item overall then has probability 1/total. For streams of 3 and 5 items, 80,000 merges gave counts between 9,903 and 10,147 for the eight items (statistic 6.34, critical value 24.32). A variant for weighted items, where the sample is drawn in proportion to the weights, assigns every item the key u ** (1 / weight) for a fresh random u in (0, 1) and keeps the k largest keys. It is worth knowing the name exists; the unweighted version is what interviews ask for.

Weighted random pick: prefix sums and binary search

The problem: given positive weights, return index i with probability w[i] / total. The beginner solutions are both expensive. Expanding the array, with i repeated w[i] times and then a uniform pick, costs memory equal to the total weight, which can be enormous. Walking the weights and subtracting from a random target costs O(n) per pick.

Derive the fast way from a picture. Lay the weights end to end on a number line from 0 to the total. Index 0 owns the first w[0] units, index 1 the next w[1], and so on. Throw a dart uniformly at the line: the chance that it lands in index i's segment is exactly its length over the total. The segment boundaries are the prefix sums, so the work is to find which segment contains the dart, and the prefix array is sorted, so binary search does it in O(log n).

Make the dart a whole number r drawn from 0 .. total - 1. Index i owns the numbers from prefix[i - 1] up to but not including prefix[i], so the answer is the first index whose prefix sum is strictly greater than r. That is a binary search you already know (an upper-bound search, see the binary search chapter), over the prefix sums you met in prefix sums.

function firstGreater(prefix, r) {
  let lo = 0;
  let hi = prefix.length - 1; // the last prefix is the total, which is always greater than r
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (prefix[mid] > r) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

class WeightedPicker {
  constructor(weights, rng) {
    this.rng = rng;
    this.prefix = [];
    let running = 0;
    for (const weight of weights) {
      running += weight;
      this.prefix.push(running);
    }
    this.total = running;
  }

  pickIndex() {
    const r = randInt(this.rng, this.total); // a whole number 0 .. total - 1
    return firstGreater(this.prefix, r);
  }
}

The setup is an O(n) pass for the prefix sums and the space is O(n). Each pick is one random draw and a binary search, O(log n). The search range ends at the last index because the final prefix, the total, is always greater than r, so the answer always exists.

Dry run: weights [1, 3, 6], prefix [1, 4, 10], total 10

One value of r maps to index 0, three to index 1, six to index 2: exactly the weights. Checking by enumeration like this is stronger than a random test, because it covers every possible draw once. A test can pass a scripted generator that returns (r + 0.5) / total for each r in turn and count where the picks land. The half avoids a rounding error at the edge when the division is not exact.

If the weights are real numbers, use rng() * total for the target and keep the same search. Rounding in the running total shifts the boundaries by tiny amounts, which is acceptable in practice. If the weights change between picks, rebuilding the prefix array costs O(n). A Fenwick tree stores prefix sums that update in O(log n) and supports a descent that finds the segment directly (see segment and Fenwick trees).

The alias method, as awareness

When there are many picks from a fixed set of weights, the alias method spends O(n) to build two small tables and then answers each pick in O(1) with two random numbers. Rescale the weights so the average is 1 and imagine n columns of height 1. Each column is filled by at most two outcomes: a small outcome (height below 1) fills part of its own column, and a large one donates the missing height, shrinking by exactly that much. Repeat until all columns are full. To pick, choose a column uniformly, then keep the column's own outcome with probability accept[column] and otherwise take its alias.

function buildAlias(weights) {
  const n = weights.length;
  const total = weights.reduce((a, b) => a + b, 0);
  const scaled = weights.map((w) => (w * n) / total); // the average column now has height 1
  const accept = new Array(n).fill(1);
  const alias = Array.from({ length: n }, (_, i) => i); // a column that is not shared points at itself
  const small = [];
  const large = [];
  scaled.forEach((height, i) => (height < 1 ? small : large).push(i));
  while (small.length > 0 && large.length > 0) {
    const s = small.pop();
    const l = large.pop();
    accept[s] = scaled[s]; // column s keeps its own outcome with this probability
    alias[s] = l; // and the rest of its height is filled by outcome l
    scaled[l] = scaled[l] + scaled[s] - 1; // l gave away 1 - scaled[s] of its height
    (scaled[l] < 1 ? small : large).push(l);
  }
  return { accept, alias };
}

function pickAlias({ accept, alias }, rng) {
  const column = randInt(rng, accept.length);
  return rng() < accept[column] ? column : alias[column];
}

For the weights [1, 3, 6, 10] the tables are accept = [0.2, 0.6, 1, 0.8] and alias = [3, 3, 2, 2]. Adding up each outcome's share over the four columns gives the exact probabilities 0.05, 0.15, 0.30 and 0.50, which are 1, 3, 6 and 10 over 20. I also checked 500 random weight lists against that sum. It is rarely asked as code in an interview. Know that it exists, that the build is O(n), and that a pick costs O(1) instead of the O(log n) of binary search.

Rejection sampling: rand10 from rand7

Rejection sampling builds a uniform choice on a target set T from a uniform choice on a bigger set U that contains it: draw from U, keep the draw if it lies in T, otherwise throw it away and draw again. Every accepted value is uniform on T. In every round each value of U is equally likely to be drawn, and whether a draw is kept depends only on whether it lies in T. So among the rounds that succeed, every value of T is equally likely: P(x) = (1/|U|) / (|T|/|U|) = 1/|T|. The expected number of rounds is |U| / |T|.

The classic exercise: you are given rand7(), returning 1 to 7 uniformly, and must build rand10(). Two natural attempts fail. Adding two calls gives 2 to 14 with a triangle of probabilities (in 100,000 trials the sum 8 came out about 14% of the time and the sum 2 about 2%). Using (rand7() + rand7()) % 10 + 1 gives counts from 8,069 to 14,200 across the ten results in my run. By the counting test, no fixed number of calls can work, so a loop is required.

Two calls make a base-7 number with two digits: (a - 1) * 7 + b takes each value from 1 to 49 with probability 1/49. The values 1 to 40 divide evenly into ten groups of four. The values 41 to 49 do not, so reject them and draw again.

function rand10(rand7) {
  while (true) {
    const index = (rand7() - 1) * 7 + rand7(); // uniform on 1 .. 49
    if (index <= 40) return 1 + ((index - 1) % 10); // 40 is a multiple of 10
  }
}

function makeRand10(rand7) {
  let leftover = 0; // uniform on 0 .. range - 1
  let range = 1;
  return function rand10() {
    while (true) {
      while (range < 10) {
        leftover = leftover * 7 + (rand7() - 1); // append one base-7 digit
        range *= 7;
      }
      const usable = range - (range % 10);
      if (leftover < usable) {
        const result = 1 + (leftover % 10);
        leftover = Math.floor(leftover / 10); // uniform on 0 .. usable / 10 - 1
        range = usable / 10;
        return result;
      }
      leftover -= usable; // rejected: still uniform on what is left
      range -= usable;
    }
  };
}

Dry run: the pairs (1,1), (6,5), (6,6), (7,7), (3,4)

Fed the script 6, 6, 7, 7, 3, 4, rand10 rejects twice and returns 8. Counting all 49 pairs, each result from 1 to 10 appears exactly four times among the 40 kept, which is the whole proof. In 100,000 seeded calls the ten counts ranged from 9,828 to 10,200 (statistic 12.20 against 27.88).

Expected cost, and what "worst case" means here

A round uses two calls and is accepted with probability 40/49. The number of rounds is geometric with mean 49/40 = 1.225, so the expected number of rand7 calls per rand10 is 2 * 49/40 = 2.45. I measured 2.456 over 100,000 results. There is no worst-case bound: the chance of t rejections in a row is (9/49)^t, which is tiny but never zero (for ten in a row it is about 4 in 100 million). The answer is always correct and only the running time is random. Algorithms with that property are called Las Vegas algorithms. Say "expected 2.45 calls, no hard cap".

The follow-up is "reduce the number of calls". The rejected values are not waste: given a reject, the leftover is itself uniform on a smaller range, and you can keep it and append more base-7 digits instead of starting over. makeRand10 keeps leftover, uniform on 0 .. range - 1, and loops until a value below the largest multiple of 10 appears. It averaged 1.497 calls per result in 200,000 runs. Information theory puts a floor of log₇ 10, about 1.18, under any method. Its output counts were uniform (statistic 12.01), and counting 200,000 pairs of consecutive results as 100 outcomes gave 102.7 against a critical value of 148.2, so successive results showed no dependence. Writing this version bug-free under pressure is hard: my first draft set the new range after an accepted value to range / 10 instead of usable / 10, and the chi-square test flagged it at once with a statistic near 3,600. In an interview, the two-call version plus the sentence "I could reuse the rejected values to cut the expected calls" is a good answer.

Random point in a circle

The problem: given a radius and a center, return a point uniformly random in the disc, meaning each region has probability in proportion to its area. Rejection sampling fits directly. Pick a point uniformly in the bounding square, which is easy, and keep it only if it falls inside the circle. The circle fills π/4 of its square, about 78.5%, so the expected number of tries is 4/π, about 1.27 (measured 1.275 over 200,000 points).

function pointInCircle(radius, cx, cy, rng) {
  while (true) {
    const x = (rng() * 2 - 1) * radius; // -radius .. radius
    const y = (rng() * 2 - 1) * radius;
    if (x * x + y * y <= radius * radius) return [cx + x, cy + y]; // keep only what falls inside the circle
  }
}

function pointInCirclePolar(radius, cx, cy, rng) {
  const angle = rng() * 2 * Math.PI;
  const distance = radius * Math.sqrt(rng()); // the square root makes equal areas equally likely
  return [cx + distance * Math.cos(angle), cy + distance * Math.sin(angle)];
}

The direct method is shorter in the number of draws but easy to get wrong. Pick a uniform angle, then a distance. The tempting choice, distance = radius * rng(), is wrong: a ring at distance d with width dd has area about 2πd * dd, which grows with d, so equal distance ranges hold unequal areas. The probability that the distance is at most d has to equal the area fraction, (d / R)². To draw a number with that distribution from a uniform u, solve u = (d / R)², which gives d = R * Math.sqrt(u).

The wrong formula puts half of all points inside the inner quarter of the area: the center is crowded. Four quadrant counts for the correct polar method were 49915, 50120, 50114 and 49851 (statistic 1.14). Both correct methods answer in O(1) expected time and O(1) space.

Random points in rectangles

Now several non-overlapping rectangles, and the point must be uniform over their union with integer coordinates, corners and edges included. Picking a rectangle at random and then a point in it is wrong: a tiny rectangle would receive as many points as a huge one. The rectangle must be chosen with probability in proportion to the number of integer points it holds, (x2 - x1 + 1) * (y2 - y1 + 1). That is a weighted pick, so reuse the previous section's machinery.

class RectanglePicker {
  constructor(rects, rng) {
    this.rects = rects; // [x1, y1, x2, y2], corners included, no two overlap
    this.rng = rng;
    this.prefix = [];
    let running = 0;
    for (const [x1, y1, x2, y2] of rects) {
      running += (x2 - x1 + 1) * (y2 - y1 + 1); // whole-number points in this rectangle
      this.prefix.push(running);
    }
  }

  pick() {
    const r = randInt(this.rng, this.prefix[this.prefix.length - 1]); // one point number out of all of them
    const i = firstGreater(this.prefix, r);
    const [x1, y1, x2] = this.rects[i];
    const offset = r - (i === 0 ? 0 : this.prefix[i - 1]); // which point inside rectangle i
    const width = x2 - x1 + 1;
    return [x1 + (offset % width), y1 + Math.floor(offset / width)];
  }
}

One draw does both jobs. r numbers all the points in the union from 0 to total - 1, rectangle by rectangle. The binary search finds the rectangle, and the remainder offset numbers the points inside it row by row: column offset % width, row floor(offset / width).

Dry run: rectangles [0,0,1,1] and [5,5,5,7]

All seven integer points appear exactly once, which I confirmed by the same enumeration on 200 random sets of non-overlapping rectangles. With 70,000 seeded picks (mulberry32(21)) the seven counts ranged from 9,925 to 10,107 (statistic 3.04, critical value 22.46). If the problem asked for a real-valued point instead, weight by area w * h and add rng() * w and rng() * h to the corner. Weighting a whole-number problem by area, or forgetting the + 1, gives wrong odds with no error to catch them.

Random pick with a blacklist

The problem: choose uniformly from 0 .. n - 1 excluding a blacklist, where n may be huge and the blacklist small, and keep the number of random calls to a minimum. Redrawing until the draw is not banned is correct rejection sampling, but when most numbers are banned the expected number of draws, n divided by the number of allowed values, is large. Building the list of allowed numbers costs O(n) memory.

Let size = n - blacklist.length be the number of allowed values. Draw once from 0 .. size - 1. Some banned numbers may lie in that range. Those are the holes, say h of them. The range below size then holds only size - h allowed numbers, so the other h allowed numbers must lie at or above size. Remap each hole to a distinct one of them.

class BlacklistPicker {
  constructor(n, blacklist, rng) {
    this.rng = rng;
    this.size = n - blacklist.length; // how many numbers are allowed
    const banned = new Set(blacklist);
    this.remap = new Map();
    let spare = this.size; // the allowed numbers at or above size are the spares
    for (const b of blacklist) {
      if (b >= this.size) continue; // banned numbers up there are never drawn
      while (banned.has(spare)) spare++;
      this.remap.set(b, spare++);
    }
  }

  pick() {
    const r = randInt(this.rng, this.size); // one call, always inside 0 .. size - 1
    return this.remap.has(r) ? this.remap.get(r) : r;
  }
}

Dry run: n = 10 with blacklists [2, 3, 5] and [1, 7, 8]

Each row lists seven different allowed numbers, one per r, so a uniform r gives a uniform allowed number. I enumerated every possible blacklist for every n up to 9, and 300 random blacklists with n up to 60 (about 60% of the numbers banned), and the check "every allowed number appears exactly once as r runs over 0 .. size - 1" held each time. In 70,000 seeded picks (mulberry32(3)) for [2, 3, 5] the seven allowed numbers came out 9,887 to 10,133 times (statistic 4.62). Build is O(blacklist size), a pick is one random call and O(1), and memory is O(blacklist size). The details that matter are skipping the banned numbers while searching for spares, and ignoring blacklist entries at or above size, which can never be drawn.

Insert, delete, getRandom: a pointer

A related design question asks for a set with O(1) insert, delete and getRandom. A hash set gives the first two but cannot return a random member without walking it. The standard answer is an array of the members plus a map from member to its index. getRandom is items[randInt(rng, items.length)]. Delete swaps the member with the last array element, updates the moved element's index in the map, and pops the end, so the array never has holes. It is uniform because every member sits in exactly one of the slots 0 .. length - 1 and the slot is chosen uniformly. The full code, the duplicates variant with a map from value to a set of indices, and the exercises are in the design problems chapter.

Randomized quickselect: expected O(n), and what "expected" means

The problem: find the k-th largest element of an unsorted array. Sorting works in O(n log n). A min-heap of size k works in O(n log k) with O(k) space. Quickselect does better on average by sorting only as much as it needs. Partition the array around a pivot, so smaller values go left and larger go right. The pivot then sits at its final sorted position. If that is the position you want, you are done. Otherwise the answer is in exactly one side, so recurse into that side alone and ignore the other. The partition steps shrink the live range from n to a part of n, and the work adds up to about a constant multiple of n instead of n log n.

The pivot rule decides the cost. If you always take the first or last element, an already sorted array is the worst case: every partition peels off one element. I measured it. With the last element as pivot on a sorted array of 20,000 numbers, looking for the minimum, the partitions examined 199,990,000 elements, essentially n²/2 = 200,000,000. With a random pivot there is no input that is bad every time: the pivot is chosen after the input is fixed, by coin flips the input's author never sees, so a bad run needs a long streak of unlucky draws on any input.

function kthLargest(nums, k, rng) {
  const a = nums.slice();
  const target = a.length - k; // where the answer sits in sorted order
  let lo = 0;
  let hi = a.length - 1;
  while (lo < hi) {
    const pivot = a[lo + randInt(rng, hi - lo + 1)]; // a random value from the live range
    let lt = lo; // a[lo .. lt - 1] < pivot
    let i = lo; // a[lt .. i - 1] === pivot
    let gt = hi; // a[gt + 1 .. hi] > pivot
    while (i <= gt) {
      if (a[i] < pivot) {
        [a[lt], a[i]] = [a[i], a[lt]];
        lt++;
        i++;
      } else if (a[i] > pivot) {
        [a[i], a[gt]] = [a[gt], a[i]];
        gt--;
      } else {
        i++;
      }
    }
    if (target < lt) hi = lt - 1;
    else if (target > gt) lo = gt + 1;
    else return pivot; // the target falls in the block of equal values
  }
  return a[lo];
}

The loop uses a three-way partition: values below the pivot go to the left block, values equal to it stay in the middle block, values above go to the right block. Three-way partition is not decoration. A two-way partition that sends all the equal values to one side degrades to n² on an array of equal elements, even with a random pivot, because every partition peels off a single element. With three blocks, all-equal input finishes in one pass: 300,000 equal values took about 1 millisecond in my run. If the target index falls inside the middle block, the pivot's value is the answer.

Dry run: kthLargest([3, 2, 1, 5, 6, 4], 2) with the script 0.2, 0.9, 0.5, 0.1

The target index in sorted order is 6 - 2 = 4 (the sorted array is 1 2 3 4 5 6, and index 4 holds 5).

It is a worked example of the invariant: the answer always lies in a[lo .. hi] and the range only shrinks. The function works on a copy, so the caller's array is untouched. The check against a sort-and-index brute force passed on 5,000 random arrays with many duplicates and negative values.

Why the expected time is O(n)

Call a pivot good if its rank among the live elements is between a quarter and three quarters. Half of the possible pivots are good, so each round is good with probability about 1/2 (ignoring rounding). A good pivot leaves at most 3/4 of the elements. Let E(n) be the largest expected total work on any input of size n, counting each element examined by a partition as one unit. Partitioning costs n. Then

E(n) <= n + (1/2) E(3n/4) + (1/2) E(n), which rearranges to E(n) <= 2n + E(3n/4).

Unrolling gives 2n * (1 + 3/4 + (3/4)² + ...) = 2n * 4 = 8n. The bound 8n is generous. Averaged over 200 random arrays, looking for the median, the partitions examined 3.45 times n elements at n = 1,000, 3.46 times n at 10,000 and 3.30 times n at 100,000 (mulberry32(2024)). A random k gave about 3.0 to 3.2 times n.

function fnv1a(text) {
  let hash = 0x811c9dc5;
  for (let i = 0; i < text.length; i++) {
    hash ^= text.charCodeAt(i);
    hash = Math.imul(hash, 0x01000193);
  }
  return hash >>> 0;
}

function inSample(key, percent) {
  return fnv1a(key) % 100 < percent; // the same key always gets the same answer
}