In this module — 8 sections
10 — Discrete mathematics
The email says this is asked more at Google than at other companies, and names combinatorics, probability and n-choose-k. It is a small topic with a high hit rate, which makes it the best return per hour on this list.
Prereqs: none · Reading: 7 min · Cards: 10
The map
Two halves. Counting answers "how many", and almost every counting question reduces to deciding whether order matters and whether repetition is allowed — that is a two-by-two grid with a formula in each cell. Probability answers "how likely", and the two ideas that do the heavy lifting are counting by complement and linearity of expectation.
Underneath both is a habit rather than a formula: when direct counting looks hard, count the opposite and subtract. That single move solves the birthday problem, most "at least one" questions, and a surprising number of the rest.
The scope is Discrete Math 101. Not olympiad material — counting, basic probability, and enough to analyse a randomised algorithm.
What decides your score here
Recognising it is a counting problem at all. Many arrive dressed as something else: "how many binary trees with n nodes" is Catalan; "how many paths through a grid" is n-choose-k.
Not ignoring the base rate. The medical-test question is the most common probability question in interviews, and the intuitive answer is wrong by a factor of two.
Using linearity of expectation. It holds even under dependence, which is what makes it powerful, and candidates who know that solve problems that otherwise look intractable.
Counting
Independent choices multiply; mutually exclusive cases add. Everything else is bookkeeping about order and repetition.
If order matters and there is no repetition, you are permuting: n! for all of them, or n!/(n−k)! for k of them. If order does not matter, divide by the k! ways of arranging the chosen ones — which gives n-choose-k, n!/(k!(n−k)!). If repetition is allowed and order matters, it is simply nᵏ.
Three identities are worth knowing rather than deriving.
C(n,k) = C(n,n−k), because choosing k is the same as
discarding the rest. C(n,k) = C(n−1,k−1) + C(n−1,k) —
Pascal's rule, which is the DP recurrence, and is why Pascal's
Triangle is a DP problem. And the sum over all k is 2ⁿ, which is the
number of subsets — the same 2ⁿ that bounds backtracking.
Use math.comb and math.perm rather than
writing factorials that overflow conceptually.
The pigeonhole principle: more items than buckets means some bucket holds at least two. That is the proof that hash collisions are unavoidable, and it settles any "show two things must share a property" question.
Inclusion-exclusion: for two sets, add them and subtract the overlap. For three, add the singles, subtract the pairs, add the triple. "How many numbers up to 100 are divisible by 3 or 5" is 33 + 20 − 6 = 47.
Catalan numbers, C(2n,n)/(n+1), count
valid parenthesisations, distinct BSTs with n nodes, and lattice paths
that stay below the diagonal. If a problem asks how many binary trees
have n nodes, the answer is Catalan, and recognising it saves you a
derivation.
Probability
The definition is favourable over total for equally likely outcomes,
and P(not A) = 1 − P(A) — which is where counting
by complement comes from, and it is very often much easier.
The birthday problem is the canonical demonstration. Twenty-three people give about a fifty percent chance of a shared birthday, which feels wrong until you notice that twenty-three people form 253 pairs. And the arithmetic is far easier by complement: one minus the probability that all birthdays differ.
Bayes is P(A|B) = P(B|A)·P(A)/P(B), and
the one instance to have memorised is the medical test. A disease
affects one percent of people; the test is ninety-nine percent accurate;
you test positive. The answer is fifty percent, not
ninety-nine — because the false positives drawn from the healthy
ninety-nine percent are as numerous as the true positives from the sick
one percent. Intuition fails because it ignores the base
rate, and that phrase is the answer.
Expectation is the sum of value times probability,
and its most useful property is linearity:
E[X + Y] = E[X] + E[Y] even when X and Y are
dependent. That is what lets you decompose a hard quantity into
indicator variables, add up their individual probabilities, and never
reason about the joint distribution. It is the single most powerful tool
in this module.
Two distributions come up. Geometric: the expected number of trials until the first success with probability p is 1/p — so a fair coin takes two flips on average. Binomial: k successes in n trials, with expectation np.
And coupon collector: gathering n distinct coupons takes about n·ln(n) draws. It answers "how many packs to complete the album" and shows up in hashing and load-balancing analysis.
The classic problems
Turning a biased coin fair (von Neumann): flip twice. Heads-then-tails means heads, tails-then-heads means tails, and a matching pair means flip again. The two mixed outcomes both have probability p(1−p), so they are equally likely regardless of the bias.
Reservoir sampling: to choose k items uniformly from a stream of unknown length, keep the first k, then for the i-th item replace a random one with probability k/i. By induction every item ends up with probability k/n. It is both a probability question and a systems question — "sample a random line from a huge file" — which is why it comes up.
Fisher-Yates: walk backwards and swap each position with a random index from the unshuffled prefix, inclusive. Drawing from the whole array instead is the classic bug: it produces nⁿ equally likely execution paths mapping onto n! permutations, and those do not divide evenly, so the distribution is biased.
Rand7 from Rand5: generate
5*(rand5()-1) + rand5() in 1..25, reject 22 to 25, take
modulo 7. The idea is rejection sampling, and the
follow-up is the expected number of attempts, 25/21.
Where this touches algorithms
Quicksort with a random pivot is n log n in expectation, by linearity. Hash table chain lengths are a probability question. A skip list's height is logarithmic in expectation because its levels come from coin flips. A bloom filter's false positive rate is a formula in m, k and n. And "power of two choices" — sampling two servers and taking the less loaded — drops maximum load from O(log n / log log n) to O(log log n), which is a load-balancing result that comes straight from this material.
Say it
Cover the answers. Out loud, in English.
Whether order matters. If it does not, divide by k! to remove the orderings, which gives n-choose-k.
More items than buckets means some bucket holds two. It proves hash collisions are unavoidable.
Because you count pairs, not people — 23 people give 253 pairs. And the arithmetic is easier by complement.
Fifty percent. The false positives from the healthy majority match the true positives. Ignoring the base rate is the error.
Because it holds even under dependence, so I can decompose into indicators and never touch the joint distribution.
Drawing the swap index from the whole array instead of the unshuffled prefix. nⁿ paths cannot map evenly onto n! permutations, so it is biased.
Now do this
Two problems and one derivation. This module rewards arithmetic practice more than code.
- Pascal's Triangle — 15 min. Name the identity you are implementing.
- Unique Paths — 20 min. Write the DP, then give the closed form as n-choose-k and say why they agree.
Then, on paper: derive the medical-test answer from scratch, and state the birthday problem by complement. Five minutes, out loud.
Stop when the base-rate answer and the complement habit come without effort.