jdfive

The Interview Prompt

The interviewer just said…

“Design a thread-safe LRU cache.”

You have a whiteboard (or a shared doc) and roughly 45 minutes. This is a Low-Level Design (LLD) prompt — not a distributed-systems deep dive on Redis or Caffeine. The interviewer wants to see how you clarify scope, pick the right data structure, define APIs, and explain a concurrency story that actually fits LRU semantics.

What you should do next

Pause. Do not open with “I’ll use Redis with TTL” or “I’ll pull in Caffeine.” That jumps past requirements and signals infrastructure before you have shown you understand the problem.

Your first move is conversational:

  1. Acknowledge the prompt.
  2. Ask clarifying questions (next chapter).
  3. State what you will deliver in the time box: requirements, data structure, get/put APIs, a working single-threaded design, then thread-safety and trade-offs.

That sequence mirrors the classic LLD delivery framework: LLD delivery in a hurry.

What LLD wants from you here

LRU cache is a compact problem that still hits real concurrency pain:

  • Clarify — capacity, miss behavior, thread-safety expectations, in-memory vs distributed
  • Data structure — HashMap + doubly linked list, or LinkedHashMap with access order
  • APIs — get(key), put(key, value), fixed capacity, evict least-recently-used on overflow
  • Concurrency story — why synchronized works, why ReadWriteLock does not, what production libraries do differently

You are not building a CDN edge cache. You are showing you can reason about compound operations, memory visibility, and lock granularity on a problem small enough to hold in your head.

A 60-second preview of the end state

When the interview is going well, you end up with something like this:

LRUCache cache = new LRUCache(3);
cache.put(1, 10);
cache.put(2, 20);
cache.put(3, 30);
cache.get(1);          // 10 — key 1 is now most recently used
cache.put(4, 40);      // evicts key 2 (LRU)
cache.get(2);          // -1 — miss

Under the hood:

  • get and put are O(1) — HashMap lookup plus constant-time pointer rewires on a doubly linked list
  • Fixed capacity — when full, the least-recently-used entry is evicted before inserting a new one
  • Thread-safe variant — every public method holds one lock so map and list always move together

That is the shape: get/put with capacity and LRU eviction, then harden it for concurrent access.