A strong answer
Setup: a table with m buckets and separate chaining holds n keys, and the hash function h is drawn at random from a family H, independently of the keys. H is universal if, for any two distinct keys x and y, Pr over h of h(x) = h(y) is at most 1/m. An example for integer keys below a prime p is h(x) = ((a·x + b) mod p) mod m with a random in 1 to p − 1 and b in 0 to p − 1.
Claim: for any fixed set of n keys and any lookup key x, the expected length of x's chain is at most 1 + n/m.
Proof: for each stored key y ≠ x, let I_y be 1 if h(y) = h(x) and 0 otherwise. The number of other keys in x's bucket is the sum of the I_y. By linearity of expectation, its expected value is the sum of Pr[h(y) = h(x)], each at most 1/m, so at most n/m. Adding x itself, if present, gives at most 1 + α with α = n/m. A lookup costs O(1) to compute the bucket plus the chain length, so O(1 + α) expected. Resizing to keep α below a constant, at O(1) amortized, makes every operation O(1) expected and amortized.
What it promises: the bound holds for every key set, including adversarial ones, because the randomness is in h, not the keys; it fails if the attacker can learn h. What it doesn't promise: a bound on any single lookup, or on the longest chain, which needs a separate high-probability argument and stronger independence.
What the interviewer is listening for
- The definition with probability over the function, not the keys.
- Indicator variables and linearity of expectation.
- The precise scope: expected, per lookup, for any fixed key set, with a secret function.
Common mistakes
- Assuming random keys instead of a random function.
- Claiming a worst-case or high-probability bound from universality alone.
- Forgetting resizing, which is what keeps α constant.