A strong answer
Huffman coding assigns each symbol a variable-length bit code, short for frequent symbols and long for rare ones, so that the encoded message is as short as possible. The codes are prefix-free, no code is the start of another, so the bit stream decodes unambiguously without separators. A prefix code is a binary tree with symbols at the leaves, and a symbol's code is its root-to-leaf path; the encoded length is the sum of frequency × depth.
Construction: put every symbol in a min-heap keyed by frequency. Repeatedly pop the two least frequent trees and push a new tree with them as children and the sum as its frequency. When one tree remains, read the codes off it. With n symbols that is O(n log n).
It is optimal among prefix codes with whole-bit lengths. Exchange argument: in some optimal tree, the two rarest symbols are sibling leaves at the deepest level, because swapping them into the deepest positions can't increase frequency × depth. Merging them into one symbol with their combined frequency leaves a smaller instance of the same problem, so the greedy step is safe at every stage.
It is used in DEFLATE (zip, gzip, PNG) after LZ77 replaces repeated strings, in JPEG and in HTTP/2 header compression. Formats transmit only code lengths and rebuild canonical codes from them. Its limit is whole-bit codes: a symbol with probability 0.9 should cost about 0.15 bits but costs at least 1, so arithmetic coding and ANS, used in Zstandard, compress skewed data better.
What the interviewer is listening for
- Prefix codes and why they decode unambiguously.
- The heap-based algorithm and its cost.
- The exchange-argument proof.
- Practical context: real formats, canonical codes and the limits.
Common mistakes
- Merging the two most frequent symbols.
- Saying Huffman achieves the entropy exactly.
- Forgetting that the decoder needs the code table.