Huffman Coding & Optimal Caching

The gap this subtopic closes

The main Greedy Algorithms subtopic teaches you to justify a greedy choice with an exchange argument or greedy-stays-ahead — but every worked example there is a single sorted linear scan. This subtopic covers two more advanced, genuinely famous greedy algorithms that don't fit that shape: Huffman coding, which builds an optimal solution bottom-up with a heap instead of top-down with a sort, and cache eviction, a case study in the opposite direction — a real, high-stakes production problem (what to evict when the cache is full) where the textbook-optimal greedy algorithm turns out to be unusable in practice, which is exactly why LRU exists as a heuristic approximation instead.

Huffman coding: optimal prefix-free compression

The problem. You have a set of symbols (characters, tokens) each with a known frequency. You want to assign each symbol a binary code such that no code is a prefix of another (so a decoder can read a bitstream unambiguously, left to right, with no delimiters) — and you want to minimize the total encoded length, weighted by frequency. Fixed-width codes (e.g., 8 bits per character in plain ASCII) waste space on frequent characters; you want frequent symbols to get short codes and rare symbols to get long codes, exactly like Morse code giving E a single dot.

The greedy algorithm. Repeatedly take the two least-frequent nodes (starting from one leaf per symbol) and merge them into a new internal node whose frequency is their sum and whose children are the two nodes you just merged; push that merged node back into the pool. Repeat until one node remains — that's the root of the Huffman tree. The code for each symbol is the sequence of left/right turns (0/1) from root to leaf.

This is a heap-driven greedy, not a sort-driven one — you never sort the whole input up front; instead you always pull the current two smallest and re-insert, which is exactly the "always-take-the-best-remaining-option" pattern the main Greedy subtopic's complexity table flags as needing a heap rather than a single sort. Minimum Cost to Connect Sticks and Minimum Cost of Ropes are literally this exact algorithm stripped of the tree/character framing: "repeatedly combine the two smallest values, summing their cost" is Huffman-tree construction, just measured by total merge cost instead of weighted code length — recognizing that these are the same shape is the single highest-leverage insight in this subtopic.

Why this is provably optimal (exchange argument sketch). Two facts drive the whole proof: (1) in any optimal prefix-free code, the two least-frequent symbols must be at the maximum depth and siblings of each other — if they weren't, you could swap them with whichever symbols are at max depth and only decrease (or keep equal) the total weighted length, since you'd be moving a low-frequency symbol to a longer code and a higher-frequency symbol to a shorter one; and (2) once you fix those two symbols as siblings, merging them into a single "combined" symbol with summed frequency reduces the problem to an identical, smaller instance. That reduction is what makes the greedy choice — always merge the current two smallest — safe at every step, by induction.

Real-world case study. Huffman coding (or an arithmetic-coding variant of the same idea) is the final compression stage inside gzip/DEFLATE, JPEG, and HTTP's Content-Encoding: gzip/br — after each format's transform step (LZ77 dictionary matching for gzip, DCT quantization for JPEG) produces a stream of symbols with a skewed frequency distribution, Huffman coding squeezes that distribution's redundancy out losslessly. This is precisely the why behind "compressed data is basically incompressible a second time" — a gzip'd file's byte distribution is already close to uniform, so there's no exploitable skew left for a second Huffman pass to find.

Optimal caching: the greedy algorithm you can't actually run

The problem. A cache has capacity for k items; a stream of accesses arrives; on a miss, you must evict something to make room. Which eviction rule minimizes total misses?

The optimal rule — Bélády's algorithm (MIN). Evict whichever item currently in the cache will be requested furthest in the future (or never again). This is provably optimal by an exchange argument nearly identical to interval scheduling's: if some other strategy evicts a different item and that item is needed sooner than the one MIN would have evicted, you can show swapping the eviction choice never increases misses, and by induction MIN dominates every other policy.

Why nobody runs it. MIN requires knowing the entire future access sequence in advance — which, for a live cache serving real traffic, you don't have. This is the practical punchline of the whole subtopic: optimal caching is a greedy algorithm with a perfect, simple correctness proof that is almost never directly implementable, because its input (the future) doesn't exist yet at decision time.

LRU is a heuristic approximation, not the optimal algorithm. Evicting the least-recently-used item is a bet that recent access patterns predict near-future ones (temporal locality) — a reasonable bet for most real workloads, but demonstrably not optimal: LRU can be made to perform arbitrarily badly with an adversarial access pattern that repeatedly cycles through more distinct items than fit in the cache (a workload where "used least recently" and "needed soonest" are anti-correlated — e.g., scanning a table larger than the cache in a loop evicts exactly the item you're about to need again). This is worth stating explicitly out loud in an interview: "LRU is a heuristic for Bélády's optimal algorithm, not the optimal algorithm itself — it approximates 'needed furthest in the future' with 'used furthest in the past,' which works well under temporal locality and fails under a scanning/cyclic access pattern." You already built the LRU cache mechanism itself (hash map + doubly linked list) in the Linked List topic's Advanced Linked List Design subtopic — this is the missing theoretical half: why that specific eviction policy was chosen over alternatives, and its formal limits.

Where this shows up in practice. Real-world systems either accept LRU's imperfection (browser caches, most OS page caches, CDN edge caches) or use refinements that approximate MIN's future-lookahead intuition more closely with observable signals — LFU (evict by lowest access frequency, which you also met in the same Linked List design subtopic), ARC (Adaptive Replacement Cache, blending recency and frequency, used in ZFS and some database buffer pools), and CLOCK/second-chance algorithms (a cheap LRU approximation used in many OS kernels that avoids LRU's exact-ordering bookkeeping cost). None of these are provably optimal — they're all informed bets about future access patterns, same as LRU, just with different heuristics for what "likely to be needed soon" means.

Complexity summary

Algorithm	Time	Space	Notes
Huffman tree construction	O(n log n)	O(n)	n = number of distinct symbols; dominated by n-1 heap pop/push pairs
Bélády's MIN (optimal caching)	O(1) amortized per access if future is known	O(k)	Not implementable online — requires the full future access sequence
LRU eviction	O(1) per access (hash map + doubly linked list)	O(k)	Heuristic approximation of MIN; no optimality guarantee

Pitfalls and interview gotchas

• Building the Huffman tree by sorting once instead of using a heap. A single upfront sort gives you the two smallest symbols correctly the first time, but every merge creates a new combined-frequency node that needs to be reinserted into sorted position — a heap handles this in O(log n) per operation; re-sorting from scratch every merge is O(n² log n).
• Forgetting the single-symbol edge case. If the input has only one distinct symbol, the "tree" is a single leaf with no root-to-leaf path — you need an explicit fallback (assign code "0") or your traversal will crash trying to walk a nonexistent tree.
• Claiming LRU is "the optimal caching algorithm." It's a very good, cheap heuristic under temporal locality — but stating this distinction (LRU approximates Bélády's MIN, and MIN itself is optimal-but-unimplementable-online) is exactly the kind of nuance that separates "I memorized LRU cache" from "I understand caching theory," and it's a common follow-up question after you finish coding an LRU cache design problem.
• Not recognizing "merge the two smallest, repeatedly" as Huffman's shape in disguise. Minimum Cost to Connect Sticks / Minimum Cost of Ropes look like generic "combine things" problems until you notice they're identical to Huffman-tree construction — missing this costs you the fast, well-understood justification ("this is provably optimal because it's Huffman-tree construction") in favor of re-deriving the exchange argument from scratch.

How to talk about this in an interview

"I'll build this bottom-up with a min-heap: repeatedly pop the two smallest-frequency nodes, merge them into a parent with their summed frequency, and push the parent back — that's Huffman-tree construction, and it's provably optimal because the two least-frequent symbols must be siblings at maximum depth in any optimal prefix code, so merging them and recursing on the smaller problem never loses optimality."

"For the caching question — the theoretically optimal eviction rule is Bélády's algorithm, evict whatever's needed furthest in the future, but that requires knowing the future access sequence, which we don't have online. LRU is the practical stand-in: it bets that recent-use predicts near-future-use, which holds for most real workloads but fails on cyclic-scan access patterns bigger than the cache — that's why systems like ZFS use ARC instead, blending recency and frequency signals rather than relying on recency alone."