System Design AI

LRU Caches in System Design Interviews: When to Use Them and What to Say

When an interview asks you to design a high-throughput service, the first place you look for latency savings is the cache. An LRU (Least Recently Used) cache is a bounded key-value store that keeps the most recent items and discards the oldest when it runs out of space. It is a concrete way to turn a few milliseconds of extra latency into a dramatic reduction in overall response time.

The problem LRU solves

Imagine you are building a URL shortener like bit.ly. The service receives billions of reads per day, but most of those reads hit a small fraction of popular links. Without a cache, every request hits the primary database, causing unnecessary load and higher latency. An LRU cache placed in front of the database stores the most recently accessed short-URL mappings. When a request arrives for a cached link, the service returns the result instantly; otherwise it falls back to the database, stores the result, and possibly evicts an older entry.

How an LRU cache works – step by step

  1. Initialize a fixed-size container (e.g., 1000 entries). Internally keep two structures:
  • A hash map key → node for O(1) look-ups.
  • A doubly linked list ordered from most-recent to least-recent.
  1. Get(key):
  • Look up the node in the hash map. If missing, miss the cache.
  • If found, move the node to the head of the linked list (most recent).
  • Return the stored value.
  1. Put(key, value):
  • If the key already exists, update the value and move the node to the head.
  • If the key is new and the cache is full, remove the tail node (the least recent) and delete its entry from the hash map.
  • Insert the new node at the head and add it to the hash map.

Small worked example

Suppose the cache capacity is 3 and the sequence of operations is: PUT(A,1) → PUT(B,2) → PUT(C,3) → GET(B) → PUT(D,4).

  • After the three puts, the order is [C, B, A] (C most recent).
  • GET(B) moves B to the front: [B, C, A].
  • PUT(D,4) sees the cache full, evicts the tail A, and inserts D at the front: [D, B, C].

The cache now holds B, C, and D, with A discarded because it was the least recently used.

Classic design questions where LRU appears

Design QuestionWhere LRU is usedReason
Content Delivery Network (CDN) edge nodeIn-memory cache of popular objectsReduces origin fetch latency for hot assets
Rate limiter (e.g., API gateway)Sliding-window counter stored per clientEvicts the counters of clients that have gone quiet, so memory stays bounded as the number of clients grows
Database read-through layerCache of recent query resultsAvoids repeated expensive joins for hot queries

In each case the cache sits between the client and the slower backing store, handling the hot path.

Trade-offs and the alternative interviewers love to probe

AspectLRU CacheAlternative (LFU, TTL, No Cache)
Eviction policySimple, approximates recency; may evict still-hot items if they are accessed less frequently.LFU evicts the least frequently used, better for bursty workloads but needs more bookkeeping.
ComplexityO(1) get/put with modest code; easy to explain.LFU often requires a priority queue or count-based buckets, increasing implementation difficulty.
Memory overheadHash map + linked list (≈ 2× entry size).LFU adds counters, increasing per-entry memory.
Staleness handlingNo built-in expiration; you must add TTL logic if needed.TTL caches automatically purge after a time, simplifying consistency but may waste space on still-hot data.

Interviewers may ask you to compare LRU with LFU or a simple TTL cache. Highlight that LRU is a good default when you care about recent access patterns and want minimal overhead. If the workload shows strong frequency skew, LFU can be justified despite the extra complexity.

A 30-second spoken pitch

"An LRU cache is a bounded key-value store that evicts the least recently accessed entry when full. It solves hot-data latency by keeping the most recent items in memory, turning expensive DB reads into cheap memory look-ups. Implement it with a hash map for O(1) look-ups and a doubly linked list to track recency. In interviews you’ll see it in CDN edge nodes, API rate limiters, and read-through DB layers. The trade-off is that it only tracks recency, so it can evict still-hot items; alternatives like LFU or TTL caches address frequency or staleness at the cost of extra complexity."

Common mistakes candidates make

  • Treating the cache as a permanent store. Forgetting that a cache is a transient layer; missing cache-miss handling leads to incorrect system behavior.
  • Ignoring cache invalidation. Updating the underlying data without propagating the change to the cache causes stale reads.
  • Over-engineering the eviction policy. Jumping straight to LFU or a custom algorithm when a simple LRU meets the requirements adds unnecessary risk.
  • Mis-sizing the cache. Picking a size without reasoning about hit-rate or memory budget; interviewers expect you to estimate a ballpark size based on traffic.
  • Forgetting thread safety. In a real service, concurrent get/put calls need synchronization; candidates often gloss over this.

How to practice this

  1. Study the worked design for an in-memory data store like Redis in the System Design AI library.
  2. Draw your own diagram on the canvas: show the client, cache layer, and origin, labeling the hash map and linked list.
  3. Explain the flow out loud using the 30-second pitch, then answer follow-up questions about eviction policy alternatives and sizing.

Questions people ask

When should I suggest an LRU cache in a design interview?

When the problem involves serving a high volume of read requests where a small fraction of items dominate traffic, such as CDN edge nodes, API rate limiters, or read-through DB layers.

How do I size an LRU cache without exact numbers?

Estimate the request rate, the fraction of hot items (often 10-20 % of total keys), and the memory each entry consumes. Choose a size that can hold the hot set while staying within the service’s memory budget.

What’s the biggest flaw of an LRU cache?

It only tracks recency, so an item that is accessed frequently but not recently can be evicted, leading to higher miss rates in workloads with strong frequency skew.

Can I combine LRU with TTL expiration?

Yes. Adding a TTL ensures stale data is removed even if it stays recent, which is useful when underlying data changes often. The implementation adds a timestamp check on each get.