Master LRU & LFU Cache Strategies for Interview Success

When interviewers ask to implement an LRU cache with O(1) complexity, many candidates only recall the need for a doubly linked list and a hash map but cannot explain the reasoning; this article walks through the full theory and hands‑on code for LRU, LFU, and Redis implementations.

Why LRU must use a doubly linked list : Deleting a node requires its predecessor; a singly linked list would need O(n) traversal, while a doubly linked list provides direct access via node.prev, achieving O(1) deletion.

O(1) LFU implementation challenges : A naïve LFU uses a min‑heap with O(log n) operations. The O(1) solution keeps two hash maps and a minFreq pointer. The difficulty lies in correctly updating minFreq —knowing when to increment or keep it unchanged is crucial, otherwise the whole algorithm fails.

Why Redis does not use a true LRU : Maintaining a global ordered list for every key would require a lock on each access, which cannot scale to Redis’s high request volume. Instead, Redis stores a 24‑bit timestamp per key and, during eviction, randomly samples a few keys (default maxmemory-samples = 5). The sampled keys’ timestamps are compared and the oldest is evicted. Raising the sample size to 10 yields near‑exact LRU behavior with minimal overhead.

Redis LFU’s “black‑tech” : Each key holds an 8‑bit counter using a Morris probabilistic counter. The counter grows logarithmically: higher frequencies increase the counter with decreasing probability, allowing roughly one million accesses to be represented within 255 values.

The article also provides a horizontal comparison of six eviction policies (including ARC and LRU‑K), ASCII diagrams showing node movements for put/get operations, complete thread‑safe implementations in Java, Go, and Python, a decision‑tree for choosing Redis eviction strategies, and five standard interview answers.

Readers are encouraged to bookmark the article and review it before interviews, as understanding the underlying structures is far more effective than memorizing conclusions.