LRU Cache

Phase 1: Requirements & Use Cases

Interviewer: "Design an LRU Cache."

Candidate: "Sure. Let me make sure I understand what we're building. An LRU — Least Recently Used — cache is a fixed-capacity data structure that evicts the least recently accessed item when capacity is exceeded. New items are inserted, and any access — read or write — marks an item as most recently used. Does that match your intent?"

Interviewer: "Yes. What are the core operations?"

Candidate: "The core operations are two: get(key) — return the value if present, -1 otherwise — and put(key, value) — insert or update a key-value pair, evicting the LRU item if we're at capacity. Both must be O(1)."

Interviewer: "What actors interact with this system?"

Candidate: "In a pure OOD sense, there's one actor: a client or calling service. The cache is a utility component. No external systems, no persistence, no concurrency for V1."

Interviewer: "What if two threads call get and put simultaneously?"

Candidate: "Good challenge. I'll scope thread safety out of V1 to keep the design clean — I'd note it as a known extension point and explain how to add it in Phase 6. The core design shouldn't change; we'd wrap operations with a lock."

WHY: Mixing concurrency logic into the core cache design obscures the fundamental O(1) structure. It's better to nail the single-threaded design first and layer thread safety on top.

Interviewer: "What about a maximum size of zero, or negative capacity?"

Candidate: "I'd treat that as a contract violation and throw an…