Interview math

When an interviewer says "n is up to a million", this table is the whole conversation. Run it in your head before proposing anything.

• Products become sums. log(ab) = log a + log b, and log(a^k) = k log a. This is why the number of digits of n is O(log n).
• The base never matters. log₂ n = log₁₀ n / log₁₀ 2: any two bases differ by a constant factor, so Big-O never names one.
• Halving is log. The number of times you can halve n before hitting 1 is log₂ n, so binary search on 10⁶ items takes about 20 probes, and on 10⁹ about 30. A balanced tree of n nodes has height about log₂ n for the same reason: doubling the data adds one hop.

Worked instance: heap sort is n pops, each pop repairs a tree of height log n, so n log n. Say it that way and the bound explains itself.

Why is a dynamic array push O(1) when a resize copies everything? Price the whole sequence of n pushes, not the unlucky one.

capacities double: 1, 2, 4, ..., n
copies across all resizes = 1 + 2 + 4 + ... + n/2  <  n
add the n pushes themselves:  under 2n writes for n pushes  =  O(1) each, amortized

Hash map resize is the same trick. Average O(1) lookup additionally assumes the hash spreads keys; the worst case is every key in one bucket, O(n). Say "average, assuming a good hash function" and you sound careful because you are. One caveat worth volunteering: if a single slow operation is unacceptable (a latency-sensitive path), an amortized bound is the wrong tool.

Costs to have cold

cost of naive recursion  ≈  branching factor ^ depth
fib(n) branches 2 ways, n deep:  2^n
memoized: n distinct states x O(1) work each  =  O(n)

• Halve, then linear work per level: n log n. Merge sort.
• Halve, then constant work: log n. Binary search.
• Halve, keep one side, linear work: n + n/2 + n/4 + ... = 2n = O(n). Quickselect on average.
• Try every subset: 2ⁿ. Every ordering: n!.

The DP sentence that always lands: cost = number of states x work per state. n states with O(n) work each is O(n²), and you said it without a recurrence.

Two identities worth owning: C(n,k) = C(n, n-k) (choosing who is in equals choosing who is out), and Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k), which is exactly the grid DP two modules down.

|A or B| = |A| + |B| - |A and B|          # subtract what you counted twice
1..100 divisible by 3 or 5:  33 + 20 - 6 = 47

Three sets: add the singles, subtract the pairwise overlaps, add back the triple. The sign alternates; that is the whole theorem.

Catalan numbers: C_n = C(2n,n) / (n+1), running 1, 1, 2, 5, 14, 42. They count balanced, nested, non-crossing structures: valid parentheses strings with n pairs, distinct BST shapes on n nodes, lattice paths that never cross the diagonal. Sanity-check with n = 3, which should give 5:

((()))   (()())   (())()   ()(())   ()()()      # 5 strings = C_3

Interview signal: if the structure is balanced or non-crossing, guess Catalan and verify the n = 3 case by hand.

Unique Paths, straight off the Blind 75: a robot walks from the top-left of an m x n grid to the bottom-right, moving only right or down. Count the paths.

every path  =  (m-1) downs and (n-1) rights, in some order
            =  choose where the downs sit among m+n-2 moves
paths       =  C(m+n-2, m-1)
3 x 7 grid:    C(3+7-2, 3-1) = C(8,2) = 8*7/2 = 28

The DP everyone writes, dp[r][c] = dp[r-1][c] + dp[r][c-1], is Pascal's rule cell by cell: the grid is Pascal's triangle, sheared. Saying that out loud converts a coding question into a counting answer. Drill the DP form at /upskill/dsa/.

From 6 engineers and 4 designers, how many 5-person teams have at least 2 designers?

sum the exact cases:
  exactly 2 designers:  C(4,2) * C(6,3)  =  6 * 20  =  120
  exactly 3 designers:  C(4,3) * C(6,2)  =  4 * 15  =   60
  exactly 4 designers:  C(4,4) * C(6,1)  =  1 * 6   =    6
  total                                             =  186

check by complement:
  all teams:            C(10,5)          =  252
  0 designers:          C(6,5)           =    6
  1 designer:           C(4,1) * C(6,4)  =   60
  252 - 6 - 60                           =  186   matches

"At least k" always means one of two routes: sum the exact cases, or subtract the shortfall from the total. When both fit in four lines, run both. Agreement is your unit test.

Bayes in the wild: a disease hits 1 in 10,000, the test is 99 percent accurate both ways. In a million people, 99 real positives drown in about 10,000 false ones, so a positive result is real about 1 time in 100. Base rates beat accuracy; say that sentence.

Expected coin flips to the first heads. Flip once; tails puts you back where you started:

E = 1 + (1/2) * E      # one flip spent; heads ends it, tails restarts it
E = 2

Expected dice rolls to the first six. Geometric with p = 1/6, so E = 1/p = 6 rolls. Rare events cost 1/p attempts; this generalizes to retries, cache misses, and randomized algorithms.

Expected fixed points of a random permutation. Let X_i be 1 if position i keeps its element:

E[X_i] = 1/n            # each element is equally likely anywhere
E[X]   = n * (1/n) = 1  # the X_i are dependent; linearity does not care

Among just 23 people, some pair shares a birthday with probability 50.7 percent. The general law: with N buckets, P(no collision among k items) is about e^-k²/2N, so collisions become likely once k reaches about 1.2 √N.

N = 365:    1.2 * √365   ≈  1.2 * 19.1  ≈  23 people
N = 2^32:   1.2 * 2^16   ≈  79,000 items   # exact 50% point is near 77,000
N = 2^64:   1.2 * 2^32   ≈  5 x 10^9 items

Translation for hash maps and id generators: a 32-bit "unique" id collides within one busy afternoon of traffic. 64 bits moves the wall to about five billion. The same math prices rolling-hash collisions in section 05.

Reservoir sampling: keep a uniform sample of k from a stream of unknown length. Keep the first k items; when item i > k arrives, keep it with probability k/i, evicting a uniformly random resident. Why it is uniform, shown for k = 1:

P(item j survives to the end)
  = (1/j) * (j/(j+1)) * ((j+1)/(j+2)) * ... * ((n-1)/n)
  = 1/n                 # everything telescopes away; every item equally likely

Fisher-Yates shuffle, the correct form:

for i = n-1 down to 1:
    j = random integer in [0, i]      # NOT [0, n-1]
    swap a[i], a[j]

This makes n * (n-1) * ... * 1 = n! equally likely outcomes, one per permutation. The tempting bug, j = random in [0, n-1] every round, produces nⁿ equally likely runs spread over n! permutations, and nⁿ is not divisible by n! (for n = 3: 27 runs onto 6 permutations), so some permutations must come up more often. That divisibility argument is the entire interview answer.

Parity in one line: popcount(x) & 1. And Kernighan's counter, while x: x &= x-1, loops once per set bit, not once per bit.

Single Number: every element appears twice except one. XOR the whole array; pairs cancel, order irrelevant, O(n) time, O(1) space.

[4,1,2,1,2]:   4 ^ 1 ^ 2 ^ 1 ^ 2  =  4

Missing Number: n distinct numbers drawn from 0..n, one missing. Two clean routes:

Gauss:  0..n sums to n(n+1)/2
        [3,0,1], n = 3:   expected 6, actual 4,  missing = 2
XOR:    (0^1^2^3) ^ (3^0^1) = 2       # every present value cancels twice

The Gauss sum deserves ten seconds of respect: pair 1 with n, 2 with n-1, and you have n/2 pairs each totalling n+1. That is why 1..100 is 5,050, and why "sum of first n integers" is O(1), never a loop.

Counting Bits: bit counts for every i from 0 to n, in O(n). Drop the last bit; you already counted the rest:

dp[i] = dp[i >> 1] + (i & 1)
i = 6 (110):  dp[6] = dp[3] + 0;  dp[3] = dp[1] + 1 = 2;  so dp[6] = 2

Reverse Bits: 32 rounds, peel from the right, build on the left:

repeat 32 times:   ans = (ans << 1) | (x & 1);   x >>= 1

Sum of Two Integers, no + allowed: XOR is the sum without carries, AND shifted left is exactly the carries. Loop until the carry dies:

while b != 0:   a, b  =  a ^ b,  (a & b) << 1
5 + 3:   (6, 2) -> (4, 4) -> (0, 8) -> (8, 0)      answer 8

10⁹+7 is prime, which unlocks modular inverses below, and it is small enough that the product of two reduced values, at most (10⁹+6)² ≈ 10¹⁸, still fits a signed 64-bit integer (max 9.2 x 10¹⁸). You can multiply then reduce without overflow. That pair of facts is the entire reason every judge uses it.

(a + b) mod m  =  (a mod m + b mod m) mod m
(a - b) mod m  =  (a mod m - b mod m + m) mod m     # the +m rescues negatives
(a * b) mod m  =  (a mod m * b mod m) mod m
a / b          =  not allowed. multiply by the inverse of b instead

Practical habit: reduce after every add and multiply inside the DP loop, and never subtract without the +m. Both bugs pass the small tests and fail the big ones.

power(a, e, m):
    r = 1;  a = a mod m
    while e > 0:
        if e is odd:  r = r * a mod m
        a = a * a mod m;  e = e >> 1
    return r

O(log e): an exponent of 10¹⁸ costs about 60 loop turns. Worked: 3¹³ mod 1000, with 13 = 1101 in binary, takes four turns and returns 323 (3¹³ = 1,594,323).

The inverse in one line, for prime m: inv(a) = power(a, m-2, m), by Fermat's little theorem. Payoff: C(n,k) mod p = n! * inv(k!) * inv((n-k)!) with factorials precomputed, which is section 02 running at n = 10⁶.

h(s) = ( s[0]*b^(n-1) + s[1]*b^(n-2) + ... + s[n-1] ) mod m     # base b ≈ 31 or 131

slide the window in O(1), dropping s[i], adding s[i+n]:
h' = ( (h - s[i]*b^(n-1)) * b + s[i+n] ) mod m                  # precompute b^(n-1) mod m

This is the engine of Rabin-Karp substring search: compare hashes in O(1), expected O(n + m) overall. Why collisions are rare: two different strings collide with probability about 1/m ≈ 10^-9 per comparison. But hash 10⁵ strings against each other and you have about 5 x 10⁹ pairs, so the birthday bound predicts a few collisions. The standard fix is two independent (base, mod) pairs, pushing odds to about 10^-18.

These are the classic rounded figures; modern hardware beats some of them, but the ratios survive, and the ratios are the answer. Each step down the table costs roughly another factor of 100 to 1,000. Caching is just refusing to move down a row.

1. Fix the inputs out loud. DAU and actions per user per day, in round numbers. Invented round numbers beat silent precise ones.
2. A day is 86,400 seconds; round to 10⁵. The rounding runs about 14 percent low on average QPS; the 3x peak factor in the next step swallows that, and it makes every division trivial.
3. Average QPS = events per day / 10⁵. Peak is 2 to 5x average; say "I will take 3x" and move on.
4. Storage = objects per day x size x retention days, then multiply by the replication factor, usually 3.
5. Bandwidth = QPS x payload size.
6. Land the sentence: "so we need N servers" or "so we need M TB". An estimate without a consequence is trivia.

100M new links per day, reads outnumber writes 10 to 1, records about 500 B (short code, long URL, owner, timestamps).

write QPS:   10^8 / 10^5                      =  1,000 avg;  x3 peak  =  3,000
read QPS:    10 * 10^8  =  10^9 / 10^5        =  10,000 avg;  x3 peak  =  30,000

5-yr store:  10^8 links/day * 365 * 5         =  1.8 * 10^11 links
             * 500 B each                     =  9 * 10^13 B   =  about 90 TB

key space:   62^7 base-62 codes               ≈  3.5 * 10^12
             vs 1.8 * 10^11 needed            =  7 chars, about 19x headroom

cache:       hot 20% of 10^9 daily reads      =  2 * 10^8 requests
             * 500 B                          =  10^11 B  =  100 GB

Land it: 90 TB over five years is a small sharded database, 100 GB of cache is a few Redis boxes, and 30,000 read QPS is a load balancer over stateless app servers. One paragraph, every number defended.

A chat app: 50M DAU, each sending 40 messages per day, messages about 100 B with metadata.

sends:       5 * 10^7 * 40                    =  2 * 10^9 msg/day
write QPS:   2 * 10^9 / 10^5                  =  20,000 avg;  x3 peak  =  60,000

storage:     2 * 10^9 * 100 B                 =  2 * 10^11 B  =  200 GB/day
             * 365                            =  73 TB/year raw
             * 3 replicas                     =  about 220 TB/year

sockets:     20% of 50M online at once        =  10^7 concurrent connections
             at 500k per gateway box          =  20 boxes;  run 30 for failover

The trap is fanout, not writes: 1-to-1 chat means deliveries roughly equal sends, another 20,000 QPS outbound. But one message to a 200-member group becomes 200 deliveries; at scale the delivery multiplier is what melts, so quote it separately. Land it: 60,000 peak write QPS partitions comfortably, 220 TB per year is a real but ordinary storage bill, and 30 gateway boxes hold the sockets.