Combinatorics and Probability for Interviews

Interviewers use counting and probability for three reasons. Some questions are about it directly ("how many ways...", "what is the chance that..."). Many system questions hide it ("how likely is a hash collision with 100,000 keys?"). And two classic algorithms are probability in disguise: the fair shuffle and sampling from a stream. This lesson gives you the rules in plain words, the formulas you need, and a Monte Carlo check for each one. (Monte Carlo means: run the random experiment many times and look at the fraction. It is not a proof, but it catches wrong formulas fast.)

A few ideas from earlier lessons help here. Floating point limits how large a count you can keep exactly (Lesson 2), and the DSA series covers the code side of subsets, permutations and backtracking (DSA Lesson 33, Subsets and Permutations, DSA Lesson 34, Backtracking). Here we care about the number of results, not generating them.

Words used in this lesson

• Outcome is one possible result of an experiment. The sample space is the set of all outcomes. An event is a group of outcomes you care about.
• Probability of an event is a number from 0 to 1. When all outcomes are equally likely it is (outcomes in the event) / (all outcomes).
• Permutation is an arrangement where order matters. Combination is a selection where order does not matter.
• n! (n factorial) is n x (n-1) x ... x 1, the number of ways to order n different things.
• n choose k is the number of ways to pick k items from n when order does not matter. Written C(n, k).
• Independent events: knowing one happened does not change the chance of the other.
• Conditional probability P(A | B) is the chance of A when you already know B happened.
• Expected value is the average result over many repeats: each value times its probability, added up.
• Uniform means every outcome has the same chance. A fair shuffle gives every ordering the same chance.

Counting rules

Product rule. If you do step 1 in a ways and then step 2 in b ways, the pair of steps can be done in a x b ways. A 4-digit PIN has 10 x 10 x 10 x 10 = 10,000 values. Sum rule. If two groups do not overlap, add them.

Permutations. n different things in a row: n! ways (n choices for the first place, n-1 for the next, and so on). Choosing and ordering k of n: n x (n-1) x ... x (n-k+1).

Combinations. Choosing k of n without order: divide the ordered count by the k! ways to reorder the chosen items.

C(n, k) = n! / (k! x (n-k)!)

Factorials grow very fast, so use BigInt. Plain numbers lose exactness above 2^53:

const fact = (n) => n <= 1n ? 1n : BigInt(n) * fact(n - 1);const perm = (n, k) => { let r = 1n; for (let i = 0; i < k; i++) r *= BigInt(n - i); return r; };function choose(n, k) { k = Math.min(k, n - k); let r = 1n; for (let i = 1; i <= k; i++) r = r * BigInt(n - k + i) / BigInt(i); return r; }console.log("3 shirts x 4 trousers:", 3 * 4, " 4-digit PIN:", 10 ** 4);console.log("8 people in a row:", fact(8), " pick 3 of 10 in order:", perm(10, 3), " unordered:", choose(10, 3));console.log("52 choose 5:", choose(52, 5), " 52!:", fact(52));console.log("Number.MAX_SAFE_INTEGER vs 21!:", Number.MAX_SAFE_INTEGER, Number(fact(21)), fact(21));

3 shirts x 4 trousers: 12  4-digit PIN: 100008 people in a row: 40320n  pick 3 of 10 in order: 720n  unordered: 120n52 choose 5: 2598960n  52!: 80658175170943878571660636856403766975289505440883277824000000000000nNumber.MAX_SAFE_INTEGER vs 21!: 9007199254740991 51090942171709440000 51090942171709440000n

The choose function multiplies and divides step by step. After step i the running value is itself a binomial coefficient, so each division is exact and the numbers stay smaller than if you computed n! first. It is a good habit when n is large.

In an interview, say the two questions out loud: "does order matter, and can items repeat?" That choice picks the row of the table.

Pascal's triangle and n choose k

Each number is the sum of the two above it. The reason: to choose k of n, either the last item is in (choose k-1 of the first n-1) or it is out (choose k of the first n-1). So C(n, k) = C(n-1, k-1) + C(n-1, k). This is also the DP recurrence when n is large and you need the answer modulo a number.

function pascal(rows) { const t = [[1]]; for (let i = 1; i < rows; i++) { const p = t[i - 1]; t.push([1, ...p.slice(1).map((v, j) => v + p[j]), 1]); } return t; }for (const r of pascal(6)) console.log(r.join(" "));const P = pascal(11); console.log(P[10][3] === Number(choose(10, 3)), P[10].reduce((a, b) => a + b), 2 ** 10);

11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1true 1024 1024

Row 10 adds up to 2^10, because choosing a subset of 10 items means choosing, for each item, in or out. That is also the number of subsets (see Lesson 4 for the bitmask view).

Stars and bars (lightly)

How many ways can you give 10 identical sweets to 4 children (a child may get none)? Draw 10 stars and 3 bars between them. Each way to place the bars is one answer, so choose the 3 bar positions out of 13 slots: C(13, 3) = 286. I checked it against three nested loops:

const bars = choose(10 + 4 - 1, 4 - 1); let brute = 0;for (let a = 0; a <= 10; a++) for (let b = 0; a + b <= 10; b++) for (let c = 0; a + b + c <= 10; c++) brute++;console.log("stars and bars:", bars, "brute force:", brute);

stars and bars: 286n brute force: 286

The same idea counts the number of non-negative integer solutions to x1 + x2 + ... + xk = n.

Inclusion-exclusion: do not count twice

If two groups overlap, adding their sizes counts the overlap twice. Subtract it once: |A or B| = |A| + |B| - |A and B|. For three groups you subtract the pairs and add back the triple, and the signs keep alternating.

Example: how many numbers from 1 to 100 are divisible by 3 or 5? 33 + 20 - 6 = 47 (the 6 is the multiples of 15).

A bigger example is derangements: arrangements of n items where no item stays in its own place. Let S_k be "k chosen items stay fixed". Inclusion-exclusion gives D(n) = sum over k of (-1)^k x n!/k!.

let cnt = 0; for (let i = 1; i <= 100; i++) if (i % 3 === 0 || i % 5 === 0) cnt++;console.log("by 3 or 5 in 1..100:", cnt, Math.floor(100 / 3) + Math.floor(100 / 5) - Math.floor(100 / 15));const der = (n) => { let s = 0n; for (let k = 0; k <= n; k++) s += (k % 2 ? -1n : 1n) * fact(n) / fact(k); return s; };console.log("derangements 1..8:", [1,2,3,4,5,6,7,8].map(der).join(" "));function bruteDer(n) { let c = 0; const used = Array(n).fill(false); (function go(i) { if (i === n) { c++; return; } for (let v = 0; v < n; v++) if (!used[v] && v !== i) { used[v] = true; go(i + 1); used[v] = false; } })(0); return c; }console.log("brute check n=7:", bruteDer(7), der(7));

by 3 or 5 in 1..100: 47 47derangements 1..8: 0 1 2 9 44 265 1854 14833brute check n=7: 1854 1854n

This is the "secret Santa where nobody draws their own name" problem. For large n the chance that a random shuffle is a derangement is about 1/e, roughly 0.37. The "fixed points" check later in this lesson is related.

Pigeonhole: some collision must happen

If you put more than m items into m boxes, at least one box has two items. It sounds too simple, but it proves things: among any 13 integers two have the same remainder when divided by 12, because there are only 12 remainders. A hash table with more keys than buckets must have a bucket with 2 keys. A lossless compressor cannot shrink every input, because there are fewer short strings than long ones.

const nums = Array.from({ length: 13 }, () => Math.floor(rnd() * 1e6)); const seen = new Map(); let pair;for (const x of nums) { if (seen.has(x % 12)) { pair = [seen.get(x % 12), x]; break; } seen.set(x % 12, x); }console.log("pigeonhole pair with equal x%12:", pair, pair[0] % 12, pair[1] % 12);

pigeonhole pair with equal x%12: [ 852465, 174813 ] 9 9

(rnd is the seeded generator defined in the next section, created with seed 42 for this run.)

The pigeonhole rule says a collision must happen once items outnumber boxes. The next section says how soon one probably happens.

The birthday paradox as hash-collision intuition

In a room of 23 people, the chance that two share a birthday is about 50%. This feels wrong, because we compare ourselves to the others (22 pairs), but the room has 253 pairs. The exact answer is easier to compute from the opposite event: the chance that all birthdays are different.

P(no match) = (d/d) x ((d-1)/d) x ((d-2)/d) x ... x ((d-n+1)/d)

Here is the exact value next to a Monte Carlo run. This is the seeded generator I use in all runs:

function mulberry32(a) { return () => { a |= 0; a = a + 0x6D2B79F5 | 0; let t = Math.imul(a ^ a >>> 15, 1 | a); t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t; return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }const rnd = mulberry32(2024);const randInt = (n) => Math.floor(rnd() * n);function pNoCollision(n, d) { let p = 1; for (let i = 0; i < n; i++) p *= (d - i) / d; return p; }for (const n of [10, 23, 50, 70]) console.log(`n=${n} exact P(shared)=${(1 - pNoCollision(n, 365)).toFixed(4)}`);function mcBirthday(n, d, trials) { let hit = 0; for (let t = 0; t < trials; t++) { const s = new Set(); for (let i = 0; i < n; i++) { const b = randInt(d); if (s.has(b)) { hit++; break; } s.add(b); } } return hit / trials; }console.log("MC n=23:", mcBirthday(23, 365, 200000).toFixed(4), "exact:", (1 - pNoCollision(23, 365)).toFixed(4));

n=10 exact P(shared)=0.1169n=23 exact P(shared)=0.5073n=50 exact P(shared)=0.9704n=70 exact P(shared)=0.9992MC n=23: 0.5065 exact: 0.5073

The useful rule: with d possible values, a collision becomes likely at about sqrt(d) items. A good approximation for a 50% chance is sqrt(2 x d x ln 2), about 1.18 x sqrt(d). This is why a "random" hash with a 32-bit output (d = 2^32, about 4.3 billion values) collides after only tens of thousands of items:

const approx = (d, p) => Math.sqrt(2 * d * Math.log(1 / (1 - p)));console.log("items for 50% collision, 2^32 space:", Math.round(approx(2 ** 32, 0.5)), " 2^64:", approx(2 ** 64, 0.5).toExponential(2));console.log("P(collision) 10000 items in 2^32:", (1 - pNoCollision(10000, 2 ** 32)).toExponential(2), " 100000 items:", (1 - pNoCollision(100000, 2 ** 32)).toFixed(3));

items for 50% collision, 2^32 space: 77163  2^64: 5.06e+9P(collision) 10000 items in 2^32: 1.16e-2  100000 items: 0.688

So a 32-bit hash with 100,000 items has about a 69% chance of at least one collision (assuming the hash is uniform, which real hashes are only close to). Practical results:

• Do not use a short hash as a unique ID for many items. Either handle collisions (compare the real values) or use a longer one. A 64-bit space needs about 5 billion items for a 50% chance.
• Hash tables expect collisions and handle them. The cost is in how many.
• The pairs matter, not the items: with n items there are about n^2 / 2 pairs, each with a tiny chance of matching. See Rabin-Karp in Lesson 7 for a use.

Expected value

The expected value is the weighted average: each outcome times its probability. A fair die has E = (1+2+3+4+5+6)/6 = 3.5. The big idea is linearity of expectation: E[X + Y] = E[X] + E[Y], even when X and Y are not independent. It lets you split a hard question into easy pieces.

const dieE = [1,2,3,4,5,6].reduce((a, b) => a + b) / 6; console.log("E[die]:", dieE, "E[sum of 2]:", 2 * dieE);let tot = 0; for (let i = 0; i < 300000; i++) tot += 1 + randInt(6) + 1 + randInt(6); console.log("MC sum of 2 dice:", (tot / 300000).toFixed(3));

E[die]: 3.5 E[sum of 2]: 7MC sum of 2 dice: 7.004

Two famous uses:

1. Fixed points in a shuffle. In a random permutation of n items, each position i has a 1/n chance of holding item i. By linearity the expected number of fixed points is n x (1/n) = 1, for any n. The positions are not independent, but linearity does not need that.
2. Coupon collector. To see all n kinds of coupons, you expect about n x H(n) draws, where H(n) = 1 + 1/2 + ... + 1/n. For n = 10 that is 29.29. It tells you how many random samples you need to touch every bucket or server.

function shuffle(a) { for (let i = a.length - 1; i > 0; i--) { const j = randInt(i + 1); [a[i], a[j]] = [a[j], a[i]]; } return a; }let fp = 0; for (let t = 0; t < 100000; t++) { const a = shuffle([...Array(10).keys()]); fp += a.filter((v, i) => v === i).length; } console.log("avg fixed points (n=10):", (fp / 100000).toFixed(3));const H = (n) => { let s = 0; for (let i = 1; i <= n; i++) s += 1 / i; return s; };function coupon(n) { const s = new Set(); let draws = 0; while (s.size < n) { s.add(randInt(n)); draws++; } return draws; }let ct = 0; for (let i = 0; i < 50000; i++) ct += coupon(10); console.log("coupon n=10 MC:", (ct / 50000).toFixed(2), "exact n*H_n:", (10 * H(10)).toFixed(2));

avg fixed points (n=10): 1.004coupon n=10 MC: 29.22 exact n*H_n: 29.29

Another interview use: expected cost of a randomised algorithm, such as quicksort with a random pivot (expected O(n log n)) or a hash table lookup (expected O(1) with a good hash). "Expected" means averaged over the algorithm's own random choices, not over the input.

Independence and conditional probability

Events A and B are independent if P(A and B) = P(A) x P(B). Many wrong answers come from assuming independence. Test it on dice: A = "the first die is even", B = "the sum is 7", C = "the sum is at least 10".

let nA = 0, nB = 0, nAB = 0, nC = 0, nAC = 0; const N = 200000;for (let t = 0; t < N; t++) { const x = 1 + randInt(6), y = 1 + randInt(6); const A = x % 2 === 0, B = x + y === 7, C = x + y >= 10; if (A) nA++; if (B) nB++; if (A && B) nAB++; if (C) nC++; if (A && C) nAC++; }console.log("P(A)", (nA / N).toFixed(3), "P(B)", (nB / N).toFixed(3), "P(A)P(B)", (nA / N * nB / N).toFixed(4), "P(A&B)", (nAB / N).toFixed(4));console.log("P(C)", (nC / N).toFixed(3), "P(A)P(C)", (nA / N * nC / N).toFixed(4), "P(A&C)", (nAC / N).toFixed(4), "exact P(C)=6/36=0.1667");

P(A) 0.501 P(B) 0.166 P(A)P(B) 0.0833 P(A&B) 0.0827P(C) 0.168 P(A)P(C) 0.0839 P(A&C) 0.1123 exact P(C)=6/36=0.1667

A and B are independent (0.0833 against 0.0827): whatever the first die shows, exactly one value of the second die makes the sum 7. A and C are not independent (0.0839 against 0.1123): a big sum is more likely when the first die is big. Independent does not mean "unrelated in meaning". It is a numeric test.

The related trap is the "gambler's fallacy": after five heads in a row, the next fair coin flip is still 50/50, because flips are independent.

Bayes in plain words: the false-positive example

Bayes' rule turns "chance of the evidence given the cause" into "chance of the cause given the evidence":

P(cause | evidence) = P(evidence | cause) x P(cause) / P(evidence)

The classic example works for any detector: a spam filter, a fraud rule, a security alert, a medical test. Say 1% of cases are real. The test finds 99% of real cases (sensitivity), and wrongly flags 5% of normal cases (false-positive rate). You get a positive. How likely is it real?

Most people say "about 99%". The honest answer is much lower. Easiest to see with natural frequencies: imagine 10,000 cases.

• 100 are real. The test flags 99 of them.
• 9,900 are normal. The test flags 5%, which is 495 of them.
• So 99 + 495 = 594 flags, but only 99 are real: 99 / 594 = 16.7%.

const prev = 0.01, sens = 0.99, fpr = 0.05;const pPos = prev * sens + (1 - prev) * fpr;console.log("P(positive):", pPos.toFixed(4), " P(sick | positive):", (prev * sens / pPos).toFixed(4));let pos = 0, sickPos = 0; const M = 2000000;for (let t = 0; t < M; t++) { const sick = rnd() < prev; const test = sick ? rnd() < sens : rnd() < fpr; if (test) { pos++; if (sick) sickPos++; } }console.log("MC P(sick | positive):", (sickPos / pos).toFixed(4), "of", pos, "positives");console.log("per 10000: sick", 10000*prev, "true pos", 10000*prev*sens, "false pos", (10000*(1-prev)*fpr).toFixed(0));

P(positive): 0.0594  P(sick | positive): 0.1667MC P(sick | positive): 0.1664 of 119287 positivesper 10000: sick 100 true pos 99 false pos 495

The lesson for engineers: when the thing you look for is rare (the base rate is low), even an accurate detector produces mostly false alarms. This is why alert rules for rare events need a very low false-positive rate, and why a Bloom filter ("probably in the set, definitely not in the set") is useful as a first check but not as the final answer.

Random sampling

Fair shuffle: Fisher-Yates

Walk from the end of the array to the start. At position i, swap with a random position j chosen from 0..i (including i). Every ordering has the same chance, 1/n!, because the choices multiply: n x (n-1) x ... x 1 = n! equally likely paths, one per ordering. A mistake that looks harmless is choosing j from the whole array each time. That gives n^n paths, which cannot be divided evenly into n! orderings, so some orderings are more likely. Another popular wrong shuffle is array.sort(() => Math.random() - 0.5): the comparison is not consistent, so the result depends on the sort algorithm. I counted the 6 orderings of 3 items over 600,000 shuffles:

function fisherYates(a) { a = [...a]; for (let i = a.length - 1; i > 0; i--) { const j = randInt(i + 1); [a[i], a[j]] = [a[j], a[i]]; } return a; }function naiveSwap(a) { a = [...a]; for (let i = 0; i < a.length; i++) { const j = randInt(a.length); [a[i], a[j]] = [a[j], a[i]]; } return a; }function sortShuffle(a) { return [...a].sort(() => rnd() - 0.5); }

Fair would be 0.1667 for each. Fisher-Yates matches. The naive swap is off: the exact counts of its 27 paths are 5, 5, 5 for three orderings and 4, 4, 4 for the other three, which gives 5/27 = 0.185 and 4/27 = 0.148, just what the table shows. The sort-based shuffle is far from fair on this engine (the original order 012 came out 37% of the time).

Reservoir sampling: a fair sample from a stream

Pick k items uniformly from a stream of unknown length, with O(k) memory, in one pass. Keep the first k. For the i-th item after that (counting from 1), pick j at random from 0..i-1. If j < k, replace slot j with the new item. Why is it fair? Item i enters with chance k/i, and it survives each later step m with chance 1 - 1/m. These multiply to k/n for every item at the end.

function reservoir(stream, k) { const r = []; let i = 0; for (const x of stream) { i++; if (r.length < k) r.push(x); else { const j = randInt(i); if (j < k) r[j] = x; } } return r; }const N = 10, K = 3, T = 300000; const hits = Array(N).fill(0);for (let t = 0; t < T; t++) for (const x of reservoir((function* () { for (let i = 0; i < N; i++) yield i; })(), K)) hits[x]++;console.log("each item chosen with prob K/N =", K / N, "->", hits.map((h) => (h / T).toFixed(3)).join(" "));

each item chosen with prob K/N = 0.3 -> 0.300 0.299 0.300 0.300 0.300 0.298 0.301 0.301 0.300 0.301

Every one of the 10 items was chosen in about 30% of the runs, from the first to the last. This is the answer to "pick a random line from a huge log file without knowing its length" (use k = 1).

Common mistakes

1. Mixing up ordered and unordered. Check by trying n = 3 by hand.
2. Double counting overlapping cases. Use inclusion-exclusion, or count the opposite event.
3. Assuming independence because events "feel" unrelated.
4. Base-rate neglect: trusting an accurate test on a rare event.
5. Using Number for factorials past 20. Use BigInt, or work modulo a prime.
6. A biased shuffle (swapping with any index, or sorting with a random comparator).
7. Trusting a simulation too much. Monte Carlo gives an estimate with noise. Use it to check a formula, not to replace one.

Interview questions

Key takeaways

• Counting starts with two questions: does order matter, and can items repeat? Then pick product, permutation, combination or stars and bars.
• C(n, k) = C(n-1, k-1) + C(n-1, k) is Pascal's triangle. Use BigInt or a DP for big values.
• Inclusion-exclusion fixes double counting. Counting the opposite event is often easier.
• Pigeonhole says a collision must happen. The birthday paradox says it happens near sqrt(d) items: about 77,000 items for a 32-bit hash.
• Expected value is additive, even without independence. Use indicator variables.
• With a rare event, an accurate test gives mostly false alarms. Use natural frequencies to explain it.
• Fisher-Yates is the fair shuffle; reservoir sampling is the fair sample from a stream.
• Check every formula with a short simulation and, where you can, a brute force.

What's next

Lesson 6: P, NP and Hard Problems: What to Say in an Interview. Counting tells you how fast the number of options grows, and that growth is the reason some problems are hard. Practise first: change the birthday code to use 64-bit style spaces, and write a brute-force check for your own counting formula before you trust it.