2. LRU Cache Intermediate

Jump to section:

A. Realistic Interview Prompt

"Design an in-memory cache with a fixed capacity that supports get and put in O(1) time. When the cache is full, evict the least-recently-used entry."

B. Difficulty

Intermediate as a pure data-structure exercise (many candidates have memorized DLL+HashMap). It becomes a genuine LLD problem — not just a DSA problem — the moment the interviewer asks for thread-safety, pluggable eviction policies, or scale, which is why it's included here despite its simple core.

C. What This Problem Tests

Choosing the right data structure combination for O(1) access + O(1) reordering
Encapsulation — hiding the linked-list/map wiring behind a clean two-method API
Recognizing when Strategy/pluggability is (and isn't) the right abstraction
Concurrency reasoning — specifically the "read that mutates" trap
API design discipline (CQS: does get need a non-mutating peek sibling?)

D. Requirements

Functional

Fixed capacity, set at construction
get(key) returns the value or a miss signal; counts as a "use" (updates recency)
put(key, value) inserts or updates; counts as a "use"
When inserting past capacity, evict the least-recently-used entry first

Non-Functional

O(1) time for both get and put
Thread-safe under concurrent access (confirm with interviewer — see E)
Extensible to other eviction policies without a full rewrite, if asked

E. Clarifying Questions

#	Question	Why It Matters	Design Decision Affected
1	What should `get` return on a miss — null, a sentinel, an exception?	Defines the API contract callers rely on	Method signature / return type
2	Is capacity fixed forever, or can it be resized at runtime?	Resizing down means potentially evicting multiple entries at once	Whether a `resize()` method exists
3	Does calling `put` on an existing key count as a "use" (update recency)?	Determines whether put always calls moveToFront	`put` implementation
4	Is this accessed by a single thread or concurrently?	The single biggest design fork for this problem	Locking strategy, or none
5	Should the eviction policy be pluggable (LRU today, LFU tomorrow)?	Determines whether to design a `Cache` interface now	Interface extraction vs. concrete class
6	Is there a TTL/expiration requirement in addition to size-based eviction?	TTL needs either lazy checks or a background sweep	Node gains an expiry field; extra component
7	Do we need a callback/listener when an entry is evicted?	E.g. write-back to a database on eviction	Observer/listener hook
8	Is this a single in-process cache, or does it need to be shared across machines?	Distributed caching (Redis-like) is a fundamentally different problem	Scoping — see Y
9	Is capacity counted by number of entries, or by total memory/weight?	Weight-based capacity changes the eviction-until-condition	Capacity accounting logic

F. Assumptions

Confirmed: fixed capacity, O(1) get/put, LRU eviction on overflow.
Assumption: both get and put on an existing key update recency.
Assumption: single-threaded core design first (V1–V3), thread-safety added explicitly (V4+) — this mirrors how the problem is actually escalated in interviews.
Assumption: capacity is entry-count based, not weight-based, unless asked.
Assumption: no TTL, no distributed scope, no persistence in the base design.

G. Actors

Actor	Responsibility
Client code / calling thread(s)	Calls `get`/`put`; in the concurrent version, multiple threads call simultaneously
Cache (System)	Maintains capacity invariant and recency order autonomously

H. Core Domain Entities

Class	Responsibility	Key Attributes	Key Methods	Does NOT Handle
`Node<K,V>`	Intrusive doubly-linked-list element holding one entry	key, value, prev, next	—	Any policy logic — it's a pure data holder
`LRUCache<K,V>`	Facade: owns the map + list, enforces capacity and recency order	capacity, `Map<K,Node>`, head/tail sentinels	`get(key)`, `put(key,value)`	Persistence, distributed coordination
`Cache<K,V>` (interface, introduced only if pluggability is requested)	Common contract so callers don't depend on a concrete eviction policy	—	`get`, `put`	How eviction actually works internally

I. Class Relationships

Composition: LRUCache owns its Node list and its map — neither outlives the cache.
Shared reference (not ownership duplication): the map's values and the linked list's nodes are the same objects — the map gives O(1) lookup, the list gives O(1) reordering. This dual-structure trick is the core insight of the whole problem.
Realization (optional): LRUCache implements Cache<K,V> only if a second implementation (e.g. LFU) is actually needed — see M for why this interface is easy to get wrong.

J. Class Diagram

View Mermaid source

classDiagram
  class LRUCache~K,V~ {
    -capacity
    -map
    -head
    -tail
    +get(K) V
    +put(K,V)
  }
  class Node~K,V~ {
    key
    value
    prev
    next
  }
  class Cache~K,V~ {
    <<interface>>
    +get(K)
    +put(K,V)
  }
  LRUCache o-- Node : head/tail + map values
  Cache <|.. LRUCache

K. Responsibility Mapping

Class	Responsibility	Does NOT Handle
Node	Holds one key/value + pointers	Any ordering decision
LRUCache	Capacity enforcement, recency ordering, lookup	Persistence, cross-process sharing

L. SOLID Analysis

Principle	How It's Applied	Naive Violation
SRP	`Node` is a pure data holder; all policy logic lives in `LRUCache`	Node with its own `evictSelf()` logic that reaches into siblings
OCP	Adding a `peek()` or listener hook doesn't require changing existing move/evict logic	Every new requirement (TTL, listener) bolted on by editing `get`/`put` directly with more if/else
LSP	If `Cache<K,V>` exists, any implementation must honor O(1)-ish semantics callers expect	An "LFU-lite" implementation that's secretly O(n) but still claims the interface
ISP	Two-method interface — nothing forced on clients they don't need	A bloated interface with `resize()`, `persist()`, `subscribe()` all mandatory
DIP	Client code can depend on `Cache<K,V>` rather than `LRUCache` directly, if swappability was requested	Client code calling `((LRUCache)cache).evictOldest()` directly, breaking the abstraction

M. Design Patterns

Pattern	Problem It Solves	Where It Appears	When NOT to Use
Facade / Encapsulation	Callers shouldn't manipulate the map or list directly	`LRUCache.get/put` hides both structures	N/A — always appropriate here
Strategy (cache-level, not field-level)	Swapping LRU for LFU entirely	A `Cache<K,V>` interface with `LRUCache`/`LFUCache` as siblings	Do not try to inject a fine-grained "EvictionPolicy" object into one fixed DLL+Map structure — LFU needs frequency buckets, not a recency list. The two policies need different backing data structures, so the correct seam is the whole class, not a plugged-in comparator. This is a case where Strategy looks tempting but doesn't cleanly fit — flag it explicitly rather than forcing it.
Decorator (optional)	Add logging/metrics around get/put without touching core logic	`MetricsCache` wrapping a `Cache<K,V>`	Skip if metrics were never asked for
Observer (optional)	Notify on eviction (e.g. write-back)	An `EvictionListener` called from inside `put`'s eviction branch	Skip unless a "notify on evict" requirement exists

N. What Is Likely to Change?

Behavior	Current Design	Anticipated Change	Protecting Abstraction
Eviction algorithm	LRU	LFU, ARC, CLOCK/approximate-LRU	`Cache<K,V>` interface (whole-class swap, not a plugged field)
Concurrency model	Single-threaded	Single lock → sharded locks	Locking is internal to `LRUCache`; public API doesn't change
Capacity accounting	Entry count	Byte/weight-based	Isolate capacity check into one method (`isOverCapacity()`) so the rule can change in one place
Persistence	None	Write-through/write-back to a store	Future `CacheWriter`/`CacheLoader` hook, not built prematurely

O. Design Evolution

V1: HashMap + DLL, fixed capacity, no eviction yet — just storage.
V2: Add eviction — when put exceeds capacity, remove the tail (LRU) node.
V3: get and put on existing keys move the node to the head (recency).
V4: Thread-safety — wrap critical sections in a single lock; explicitly reason about why "readers don't need a lock" is wrong here (see W).
V5: Reduce contention — shard into N independent sub-caches by hash(key) % N, each with its own lock; global order becomes approximate.
V6: Pluggability — extract Cache<K,V> interface if a second policy (LFU) is genuinely required, accepting that it's a whole-class swap, not a strategy field.

What stays stable: the two-method public API (get/put). Internal locking granularity and eviction bookkeeping evolve underneath it without callers noticing.

P. API / Interface Design

interface Cache<K, V> {
  Optional<V> get(K key);
  void        put(K key, V value);
}

class LRUCache<K, V> implements Cache<K, V> {
  LRUCache(int capacity);            // throws IllegalArgumentException if capacity <= 0
  Optional<V> get(K key);           // O(1); updates recency
  void        put(K key, V value);   // O(1); may trigger eviction
}

interface Cache<K, V> {
  Optional<V> get(K key);
  void put(K key, V value);
}

class LRUCache<K, V> implements Cache<K, V> {
  LRUCache(int capacity) { }   // throws IllegalArgumentException if capacity <= 0
  public Optional<V> get(K key) { throw new UnsupportedOperationException(); }        // O(1); updates recency
  public void put(K key, V value) { throw new UnsupportedOperationException(); }      // O(1); may trigger eviction
}

template <typename K, typename V>
class Cache {
public:
  virtual std::optional<V> get(const K& key) = 0;
  virtual void put(const K& key, const V& value) = 0;
};

template <typename K, typename V>
class LRUCache : public Cache<K, V> {
public:
  explicit LRUCache(int capacity);          // throws std::invalid_argument if capacity <= 0
  std::optional<V> get(const K& key);       // O(1); updates recency
  void put(const K& key, const V& value);   // O(1); may trigger eviction
};

class Cache {
  get(key) { throw new Error('not implemented'); }
  put(key, value) { throw new Error('not implemented'); }
}

class LRUCache extends Cache {
  constructor(capacity) { super(); }   // throws Error if capacity <= 0
  get(key) { throw new Error('not implemented'); }         // O(1); updates recency
  put(key, value) { throw new Error('not implemented'); }  // O(1); may trigger eviction
}

interface Cache<K, V> {
  get(key: K): V | null;
  put(key: K, value: V): void;
}

class LRUCache<K, V> implements Cache<K, V> {
  constructor(capacity: number) { }   // throws Error if capacity <= 0
  get(key: K): V | null { throw new Error('not implemented'); }         // O(1); updates recency
  put(key: K, value: V): void { throw new Error('not implemented'); }   // O(1); may trigger eviction
}

Ownership/validation notes: returning Optional<V> (or a language-appropriate nullable/sentinel) avoids ambiguity between "missing key" and "value is actually null." Capacity is validated once, at construction, not on every operation.

Q. Pseudocode — Critical Logic

get(key):
  node = map.get(key)
  if node is null: return MISS
  moveToHead(node)
  return node.value

put(key, value):
  node = map.get(key)
  if node exists:
    node.value = value
    moveToHead(node)
    return
  newNode = Node(key, value)
  map[key] = newNode
  addToHead(newNode)
  if map.size() > capacity:
    lru = tail.prev
    removeNode(lru)
    map.remove(lru.key)

public Optional<V> get(K key) {
  Node<K, V> node = map.get(key);
  if (node == null) return Optional.empty();   // MISS
  moveToHead(node);
  return Optional.of(node.value);
}

public void put(K key, V value) {
  Node<K, V> node = map.get(key);
  if (node != null) {
    node.value = value;
    moveToHead(node);
    return;
  }
  Node<K, V> newNode = new Node<>(key, value);
  map.put(key, newNode);
  addToHead(newNode);
  if (map.size() > capacity) {
    Node<K, V> lru = tail.prev;
    removeNode(lru);
    map.remove(lru.key);
  }
}

std::optional<V> get(const K& key) {
  auto it = map.find(key);
  if (it == map.end()) return std::nullopt;   // MISS
  moveToHead(it->second);
  return it->second->value;
}

void put(const K& key, const V& value) {
  auto it = map.find(key);
  if (it != map.end()) {
    it->second->value = value;
    moveToHead(it->second);
    return;
  }
  auto newNode = std::make_shared<Node>(key, value);
  map[key] = newNode;
  addToHead(newNode);
  if (map.size() > capacity) {
    auto lru = tail->prev;
    removeNode(lru);
    map.erase(lru->key);
  }
}

get(key) {
  const node = this.map.get(key);
  if (node === undefined) return MISS;
  this.moveToHead(node);
  return node.value;
}

put(key, value) {
  const node = this.map.get(key);
  if (node !== undefined) {
    node.value = value;
    this.moveToHead(node);
    return;
  }
  const newNode = new Node(key, value);
  this.map.set(key, newNode);
  this.addToHead(newNode);
  if (this.map.size > this.capacity) {
    const lru = this.tail.prev;
    this.removeNode(lru);
    this.map.delete(lru.key);
  }
}

get(key: K): V | typeof MISS {
  const node = this.map.get(key);
  if (node === undefined) return MISS;
  this.moveToHead(node);
  return node.value;
}

put(key: K, value: V): void {
  const node = this.map.get(key);
  if (node !== undefined) {
    node.value = value;
    this.moveToHead(node);
    return;
  }
  const newNode = new Node<K, V>(key, value);
  this.map.set(key, newNode);
  this.addToHead(newNode);
  if (this.map.size > this.capacity) {
    const lru = this.tail.prev;
    this.removeNode(lru);
    this.map.delete(lru.key);
  }
}

R. End-to-End Use Case

capacity = 2
put(1,"a")  → list: [1]                map:{1}
put(2,"b")  → list: [2,1]              map:{1,2}
get(1)      → moves 1 to head → [1,2]  returns "a"
put(3,"c")  → over capacity → evict tail (2) → [3,1]   map:{1,3}
get(2)      → MISS (was evicted)

S. Data Structures

Structure	Used For	Why	Alternative & Trade-off
`HashMap<K, Node>`	O(1) key lookup	Direct pointer to the node, no scanning	TreeMap by last-access time — O(log n), unnecessary here
Doubly linked list w/ head+tail sentinels	O(1) reordering and O(1) tail eviction	Sentinels avoid null-checks at the boundaries	Singly linked list — can't remove an arbitrary node in O(1) without a prev pointer

T. Complexity Analysis

Operation	Time	Space
`get`	O(1)	O(1) extra
`put`	O(1)	O(1) extra
Overall storage	—	O(capacity)

U. Testing Strategy

Happy path: put then get returns the same value; recency order updates correctly.
Edge cases: capacity = 1; put on an already-full cache with a brand-new key evicts exactly one; repeated get on the same key never evicts it.
Invalid input: capacity ≤ 0 at construction should be rejected.
Concurrency tests: N threads hammering get/put — assert size never exceeds capacity and no node ever appears twice in the list (structural corruption check), even though exact eviction order under a race is not required to be deterministic.

V. Interviewer Follow-Ups

Follow-Up	Testing	Design Change	Classes Changed	Pattern/Trade-off
"Make it thread-safe."	Concurrency reasoning	Guard get/put with one exclusive lock	`LRUCache`	Must realize `get` mutates (moveToHead) — a read-write lock optimization is a bug here, not an improvement
"Now support LFU, switchable at runtime."	Recognizing pattern limits	Extract `Cache<K,V>`; write a separate `LFUCache` with frequency buckets	New class, not a plugged field	Strategy at the class level, not the field level (see M)
"Needs to hold a billion entries — one process won't fit."	LLD → HLD boundary	Recognize this is now a distributed cache problem	None in-process — infra/service change	Consistent hashing, replication — out of LLD scope
"Add TTL to entries."	State/lifecycle extension	Node gains an expiry timestamp; check lazily on access or sweep periodically	`Node`, `LRUCache.get`	Lazy-check is simpler; background sweep is more proactive but adds a thread to reason about
"Reduce lock contention under heavy concurrent load."	Scalability under concurrency	Shard into N sub-caches, each with its own lock, keyed by `hash(key) % N`	`LRUCache` wrapped by a `ShardedCache`	Global LRU order becomes approximate — trade precision for throughput
"What if two threads both try to insert the same brand-new key at once?"	Atomicity of check-then-act	The existence-check + insert must happen inside the same locked section	`LRUCache.put`	Classic check-then-act race if split across two lock acquisitions
"Add an eviction callback for write-back to a database."	Extensibility via hooks	An `EvictionListener` invoked when a node is removed	`LRUCache` gains an optional listener field	Call the listener outside the lock to avoid holding it during I/O
"I want to inspect the LRU value without affecting its recency."	API design / CQS discipline	Add a non-mutating `peek(key)`	`LRUCache`	Keeps `get`'s contract ("get counts as use") intact and explicit
"Persist cache contents across restarts."	Persistence trade-offs	Serialize order + entries on shutdown, or treat cache purely as derived/rebuildable state	New (de)serialization path	Often simpler to just accept a cold cache after restart than to persist a cache correctly

W. Concurrency

The central insight: get is not a pure read — it mutates the linked list (moveToHead). Treating it as read-only and reaching for a read-write lock (letting concurrent "readers" proceed together) is a classic, subtle bug: two concurrent "reads" can corrupt the list pointers.

Simplest correct approach: one exclusive lock (mutex/synchronized) guarding both get and put entirely.
Reducing contention: shard into N independent caches by key hash, each with its own lock — same idea used internally by structures like ConcurrentHashMap. Global recency order becomes approximate across shards, which is an accepted trade-off.
Why plain atomics aren't enough: updating a DLL node touches multiple pointers (prev/next on up to three nodes) — not a single atomic word, so std::atomic alone can't make this safe without a lock or a much more complex lock-free list.
Real-world alternative: production caches (e.g. Caffeine) use approximate recency (CLOCK-like sampling) specifically to avoid taking a lock on every access — worth mentioning as the "senior" answer if pushed on extreme throughput, without over-claiming you'd implement it from scratch in an interview.

X. Persistence

Caches are usually intentionally volatile — the source of truth lives elsewhere (DB), and the cache is just an optimization. If persistence is explicitly requested: introduce a CacheLoader (read-through on miss) and/or CacheWriter (write-through/write-back on put), and be explicit that persisted "cache" state is a performance optimization, not a durability guarantee — losing it on crash should be an acceptable, recoverable event, not a data-loss incident.

Y. Scaling Boundary

Layer	What Belongs Here
LLD	This class: map+list, eviction, in-process locking
HLD	A caching service/tier (Redis-like), client libraries, cache invalidation strategy
Distributed Systems	Consistent hashing across cache nodes, replication, handling node failure without losing all cached data at once

Z. Failure Scenarios

Process crash: all cached data is lost by design — the system must tolerate a cold cache and repopulate from the source of truth.
Partial mutation on crash mid-eviction: only relevant if persisted; in-memory-only designs don't need to reason about this.
Listener/write-back failure on eviction: should not block or corrupt the cache itself — failures in a listener must be isolated (e.g., caught and logged, not propagated to break put).

AA. Common Bad Designs

ArrayList + linear shift for order — looks intuitive, but shifting elements on every access is O(n), defeating the entire point of the problem.
Sorting by a stored "last accessed" timestamp at eviction time — looks clever (avoids a linked list), but makes eviction O(n log n) instead of O(1), and still needs a way to look up entries by key.
Read-write lock "optimization" — looks like a throughput win ("reads don't block each other"), but is actually incorrect here because get mutates state (see W).
A generic pluggable "EvictionPolicy" interface bolted onto one fixed DLL+Map structure — looks extensible, but LFU/ARC genuinely need different backing structures, so the abstraction leaks or becomes dishonestly slow. Better to swap the whole class via a Cache<K,V> interface.

AB. Design Trade-Offs

Decision	Option A	Option B	Trade-off
Ordering structure	Doubly linked list	Sorted map by timestamp	DLL is O(1) for reorder/evict; sorted map is O(log n) but avoids pointer bookkeeping
Concurrency control	Single global lock	Sharded locks	Global lock is simple and exactly correct; sharding trades exact global LRU order for throughput
Eviction policy extensibility	Whole-class Strategy (`Cache<K,V>`)	Field-level policy injection into one structure	Whole-class swap is honest about differing internal structures; field injection looks elegant but breaks down for LFU

AC. Interviewer Evaluation

Weak candidate: uses an array/list with linear scans; doesn't recognize the O(1) requirement drives the whole design.
Average candidate: correct HashMap+DLL design, but doesn't proactively mention thread-safety or ask about it.
Strong candidate: correct design, asks about concurrency requirements unprompted, and explains why get is "secretly a write."
Exceptional candidate: all of the above, plus recognizes that naive policy-pluggability (LRU→LFU) doesn't fit a field-injection model, and can discuss sharding/approximate-LRU trade-offs at scale without being asked.

AD. Interview Simulation

Interviewer: Design an LRU cache with O(1) get and put.

Candidate: I'll use a hash map for O(1) lookup and a doubly linked list for O(1) reordering — the map's values and the list's nodes will be the same objects.

Interviewer: Walk me through put when the cache is full.

Candidate: Insert the new node at the head, then if size exceeds capacity, remove the tail's previous node — that's the least recently used — and delete it from the map too.

Interviewer: Now make it thread-safe.

Candidate: I'd guard both get and put with a single exclusive lock. It's worth calling out explicitly: get isn't read-only here, it moves the node to the head, so a read-write lock would actually be a bug, not an optimization.

Interviewer: Good catch. Now, high contention — thousands of threads hitting this every millisecond.

Candidate: I'd shard into N independent LRU caches by hashing the key, each with its own lock — similar to how ConcurrentHashMap works internally. The trade-off is the LRU order becomes approximate across the whole cache rather than globally exact.

Interviewer: Now I want LFU as an alternative, switchable at runtime.

Candidate: I wouldn't try to inject an eviction-policy object into this same map+list structure — LFU needs frequency buckets, a genuinely different backing structure. I'd extract a Cache<K,V> interface and write LFUCache as a sibling implementation instead.

Interviewer: Last one — a billion entries, way past one machine's memory.

Candidate: That's outside LLD at that point — it becomes a distributed cache with consistent hashing and replication across nodes. The class design here stays the same per-node; the system around it changes.

AE. Online Solution Comparison

Source	Approach	Strength	Weakness	Worth Learning
ashishps1/awesome-low-level-design (GitHub)	HashMap + DLL, `synchronized` methods for thread safety, helper methods (`addToHead`, `removeTail`)	Clean, minimal, multi-language reference implementations	Doesn't explore sharding or LFU extensibility	The helper-method decomposition (addToHead/removeNode/moveToHead) keeps the core logic readable
Medium — Thread-Safe LRU Cache in Java	Explicit discussion of the "get mutates, so RW-lock is wrong" trap; proposes sharded buckets each with its own lock	Best concurrency-specific reasoning of the sources found	Lighter on the base data-structure walkthrough	The explicit "get is a write" framing — central to this document's W section
AlgoMonster / AlgoMaster (cross-referenced, not deep-fetched)	Standard DLL+map walkthroughs with interview framing	Good for a first-pass mental model	Mentions Strategy/Singleton patterns somewhat by rote rather than derived from a requirement	Useful as a sanity check against the synthesized design here

AF. Interview Cheat Sheet

Problem	LRU Cache
Difficulty	Intermediate (Advanced+Concurrency once thread-safety is asked)
Core requirements	Fixed capacity, O(1) get/put, evict LRU on overflow
Key clarifications	Thread-safety needed? Pluggable eviction policy? TTL? Weight-based capacity?
Core entities	Node, LRUCache (map + DLL), optional Cache<K,V> interface
Key relationships	Map values and DLL nodes are the same shared objects
Key patterns	Facade; whole-class Strategy for alternate policies (not field-level)
Most important decision	Recognizing get mutates state — drives the entire concurrency story
Likely-changing behavior	Eviction algorithm, concurrency model, capacity accounting
Concurrency concern	get-is-a-write; RW-lock is a bug, not an optimization; sharding trades exactness for throughput
Top follow-ups	Thread-safety, LFU swap, TTL, eviction callback, billion-entry scale (HLD boundary)
Common mistakes	ArrayList shifting, RW-lock misuse, forcing a generic eviction-policy field
What NOT to over-engineer	Persistence, distributed coordination — unless explicitly asked

AG. Full Implementation

A complete, compilable reference implementation of every class in the diagram above (composition, inheritance, interface realization, and dependency-injected strategies all preserved per section I), with a runnable demo exercising the primary flow — in Java, C++, JavaScript, and TypeScript.

// LRU Cache - full LLD implementation (single-file demo).
// Difficulty badge is plain "Intermediate" (no Concurrency tag), so this stays
// single-threaded and simple - no locks.
import java.util.*;

public class p2 {

    // ---------- Cache (interface) ----------
    // Exists so callers can depend on a contract rather than the concrete LRU
    // implementation - e.g. an LFU variant could implement this same interface later.
    interface Cache<K, V> {
        Optional<V> get(K key);
        void put(K key, V value);
    }

    // ---------- Node ----------
    // Pure intrusive doubly-linked-list element; holds no policy logic of its own.
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }

    // ---------- LRUCache ----------
    static class LRUCache<K, V> implements Cache<K, V> {
        private final int capacity;
        // Map gives O(1) lookup; the list (via the same Node objects) gives O(1) reordering.
        // This dual-structure trick is the core insight of the whole problem.
        private final Map<K, Node<K, V>> map;
        private final Node<K, V> head; // sentinel; head.next = most-recently-used
        private final Node<K, V> tail; // sentinel; tail.prev = least-recently-used

        LRUCache(int capacity) {
            if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
            this.capacity = capacity;
            this.map = new HashMap<>();
            this.head = new Node<>(null, null);
            this.tail = new Node<>(null, null);
            head.next = tail;
            tail.prev = head;
        }

        public Optional<V> get(K key) {
            Node<K, V> node = map.get(key);
            if (node == null) return Optional.empty();
            moveToHead(node);
            return Optional.of(node.value);
        }

        public void put(K key, V value) {
            Node<K, V> existing = map.get(key);
            if (existing != null) {
                existing.value = value;
                moveToHead(existing);
                return;
            }
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            if (map.size() > capacity) {
                Node<K, V> lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        }

        // ---- internal list helpers ----
        private void addToHead(Node<K, V> node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        private void removeNode(Node<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void moveToHead(Node<K, V> node) {
            removeNode(node);
            addToHead(node);
        }

        int size() { return map.size(); }
    }

    // ---------- Demo ----------
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1, "a");
        cache.put(2, "b");
        System.out.println("get(1) = " + cache.get(1)); // Optional[a], 1 is now most recent

        cache.put(3, "c"); // capacity exceeded -> evicts key 2 (least recently used)
        System.out.println("get(2) = " + cache.get(2)); // Optional.empty (evicted)
        System.out.println("get(3) = " + cache.get(3)); // Optional[c]

        cache.put(1, "a-updated"); // update existing key, also refreshes recency
        System.out.println("get(1) = " + cache.get(1)); // Optional[a-updated]

        System.out.println("final size = " + cache.size());
    }
}

// LRU Cache - full LLD implementation (single-file demo).
// Difficulty badge is plain "Intermediate" (no Concurrency tag), so this stays
// single-threaded and simple - no locks/mutexes.
#include <iostream>
#include <unordered_map>
#include <optional>
#include <stdexcept>
#include <string>

// ---------- Node ----------
// Pure intrusive doubly-linked-list element; holds no policy logic of its own.
template <typename K, typename V>
struct Node {
    K key;
    V value;
    Node* prev = nullptr;
    Node* next = nullptr;
    Node() = default;
    Node(K k, V v) : key(std::move(k)), value(std::move(v)) {}
};

// ---------- Cache (interface) ----------
// Exists so callers can depend on a contract rather than the concrete LRU
// implementation - e.g. an LFU variant could implement this same interface later.
template <typename K, typename V>
class Cache {
public:
    virtual ~Cache() = default;
    virtual std::optional<V> get(const K& key) = 0;
    virtual void put(const K& key, const V& value) = 0;
};

// ---------- LRUCache ----------
template <typename K, typename V>
class LRUCache : public Cache<K, V> {
public:
    explicit LRUCache(int capacity) : capacity(capacity) {
        if (capacity <= 0) throw std::invalid_argument("capacity must be > 0");
        head = new Node<K, V>();
        tail = new Node<K, V>();
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache() override {
        Node<K, V>* cur = head;
        while (cur) {
            Node<K, V>* next = cur->next;
            delete cur;
            cur = next;
        }
    }

    std::optional<V> get(const K& key) override {
        auto it = map.find(key);
        if (it == map.end()) return std::nullopt;
        Node<K, V>* node = it->second;
        moveToHead(node);
        return node->value;
    }

    void put(const K& key, const V& value) override {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->value = value;
            moveToHead(it->second);
            return;
        }
        Node<K, V>* newNode = new Node<K, V>(key, value);
        map[key] = newNode;
        addToHead(newNode);
        if (static_cast<int>(map.size()) > capacity) {
            Node<K, V>* lru = tail->prev;
            removeNode(lru);
            map.erase(lru->key);
            delete lru;
        }
    }

    size_t size() const { return map.size(); }

private:
    void addToHead(Node<K, V>* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(Node<K, V>* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(Node<K, V>* node) {
        removeNode(node);
        addToHead(node);
    }

    int capacity;
    std::unordered_map<K, Node<K, V>*> map; // O(1) lookup; list (same Node objects) gives O(1) reordering
    Node<K, V>* head; // sentinel; head->next = most-recently-used
    Node<K, V>* tail; // sentinel; tail->prev = least-recently-used
};

// ---------- Demo ----------
int main() {
    LRUCache<int, std::string> cache(2);
    cache.put(1, "a");
    cache.put(2, "b");
    auto v1 = cache.get(1);
    std::cout << "get(1) = " << (v1 ? *v1 : "MISS") << "\n"; // "a", 1 is now most recent

    cache.put(3, "c"); // capacity exceeded -> evicts key 2 (least recently used)
    auto v2 = cache.get(2);
    std::cout << "get(2) = " << (v2 ? *v2 : "MISS") << "\n"; // MISS (evicted)
    auto v3 = cache.get(3);
    std::cout << "get(3) = " << (v3 ? *v3 : "MISS") << "\n"; // "c"

    cache.put(1, "a-updated"); // update existing key, also refreshes recency
    auto v4 = cache.get(1);
    std::cout << "get(1) = " << (v4 ? *v4 : "MISS") << "\n"; // "a-updated"

    std::cout << "final size = " << cache.size() << "\n";
    return 0;
}

// LRU Cache - full LLD implementation (single-file demo).
// Difficulty badge is plain "Intermediate" (no Concurrency tag), so this stays
// single-threaded and simple - no locks.

// A sentinel "miss" value distinct from any legitimate stored value (including
// undefined/null), so callers can tell "not found" apart from "found, value is null".
const MISS = Symbol("MISS");

// ---------- Cache (interface, documented via JSDoc since JS has no interfaces) ----------
// Exists so callers can depend on a contract rather than the concrete LRU
// implementation - e.g. an LFU variant could implement this same interface later.
/**
 * @interface Cache
 * get(key) -> value or MISS
 * put(key, value) -> void
 */

// ---------- Node ----------
// Pure intrusive doubly-linked-list element; holds no policy logic of its own.
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// ---------- LRUCache ----------
class LRUCache {
  constructor(capacity) {
    if (capacity <= 0) throw new Error("capacity must be > 0");
    this.capacity = capacity;
    // Map gives O(1) lookup; the list (via the same Node objects) gives O(1) reordering.
    // This dual-structure trick is the core insight of the whole problem.
    this.map = new Map();
    this.head = new Node(null, null); // sentinel; head.next = most-recently-used
    this.tail = new Node(null, null); // sentinel; tail.prev = least-recently-used
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return MISS;
    this._moveToHead(node);
    return node.value;
  }

  put(key, value) {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this._moveToHead(existing);
      return;
    }
    const newNode = new Node(key, value);
    this.map.set(key, newNode);
    this._addToHead(newNode);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this._removeNode(lru);
      this.map.delete(lru.key);
    }
  }

  size() { return this.map.size; }

  // ---- internal list helpers ----
  _addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  _removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _moveToHead(node) {
    this._removeNode(node);
    this._addToHead(node);
  }
}

// ---------- Demo ----------
function main() {
  const cache = new LRUCache(2);
  cache.put(1, "a");
  cache.put(2, "b");
  console.log("get(1) =", cache.get(1)); // "a", 1 is now most recent

  cache.put(3, "c"); // capacity exceeded -> evicts key 2 (least recently used)
  console.log("get(2) =", cache.get(2) === MISS ? "MISS" : cache.get(2)); // MISS (evicted)
  console.log("get(3) =", cache.get(3)); // "c"

  cache.put(1, "a-updated"); // update existing key, also refreshes recency
  console.log("get(1) =", cache.get(1)); // "a-updated"

  console.log("final size =", cache.size());
}

if (require.main === module) {
  main();
}

module.exports = { Node, LRUCache, MISS };

// LRU Cache - full LLD implementation (single-file demo).
// Difficulty badge is plain "Intermediate" (no Concurrency tag), so this stays
// single-threaded and simple - no locks.

// ---------- Cache (interface) ----------
// Exists so callers can depend on a contract rather than the concrete LRU
// implementation - e.g. an LFU variant could implement this same interface later.
// Optional<V> is modeled as V | undefined since TS has no built-in Optional type.
interface Cache<K, V> {
  get(key: K): V | undefined;
  put(key: K, value: V): void;
}

// ---------- Node ----------
// Pure intrusive doubly-linked-list element; holds no policy logic of its own.
class Node<K, V> {
  prev: Node<K, V> | null = null;
  next: Node<K, V> | null = null;
  constructor(public key: K | null, public value: V | null) {}
}

// ---------- LRUCache ----------
class LRUCache<K, V> implements Cache<K, V> {
  private readonly capacity: number;
  // Map gives O(1) lookup; the list (via the same Node objects) gives O(1) reordering.
  // This dual-structure trick is the core insight of the whole problem.
  private readonly map: Map<K, Node<K, V>> = new Map();
  private readonly head: Node<K, V>; // sentinel; head.next = most-recently-used
  private readonly tail: Node<K, V>; // sentinel; tail.prev = least-recently-used

  constructor(capacity: number) {
    if (capacity <= 0) throw new Error("capacity must be > 0");
    this.capacity = capacity;
    this.head = new Node<K, V>(null, null);
    this.tail = new Node<K, V>(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.moveToHead(node);
    return node.value as V;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.moveToHead(existing);
      return;
    }
    const newNode = new Node<K, V>(key, value);
    this.map.set(key, newNode);
    this.addToHead(newNode);
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev as Node<K, V>;
      this.removeNode(lru);
      this.map.delete(lru.key as K);
    }
  }

  size(): number { return this.map.size; }

  // ---- internal list helpers ----
  private addToHead(node: Node<K, V>): void {
    node.prev = this.head;
    node.next = this.head.next;
    (this.head.next as Node<K, V>).prev = node;
    this.head.next = node;
  }

  private removeNode(node: Node<K, V>): void {
    (node.prev as Node<K, V>).next = node.next;
    (node.next as Node<K, V>).prev = node.prev;
  }

  private moveToHead(node: Node<K, V>): void {
    this.removeNode(node);
    this.addToHead(node);
  }
}

// ---------- Demo ----------
function main(): void {
  const cache = new LRUCache<number, string>(2);
  cache.put(1, "a");
  cache.put(2, "b");
  console.log("get(1) =", cache.get(1)); // "a", 1 is now most recent

  cache.put(3, "c"); // capacity exceeded -> evicts key 2 (least recently used)
  console.log("get(2) =", cache.get(2) ?? "MISS"); // MISS (evicted)
  console.log("get(3) =", cache.get(3)); // "c"

  cache.put(1, "a-updated"); // update existing key, also refreshes recency
  console.log("get(1) =", cache.get(1)); // "a-updated"

  console.log("final size =", cache.size());
}

main();

export { Node, LRUCache, Cache };

← 1. Parking Lot 3. Rate Limiter →