Design an LRU Cache

Problem Design and implement a fixed-capacity Least Recently Used cache. When a write would exceed capacity, the least recently used entry is evicted. Both reads and writes must run in O(1).

Requirements

• get(key) -> value? — returns the value and marks the entry most recently used; miss returns null/absent
• put(key, value) -> void — inserts or updates, marks most recently used, evicts the LRU entry when over capacity
• size() -> int, and optionally remove(key) and clear()
• Strict O(1) for both get and put — not amortized-by-scan

Core design

• Two structures working together: a hash map from key -> node pointer for O(1) lookup, and a doubly linked list ordered by recency with most-recently-used at the head and least-recently-used at the tail.
• Neither structure alone suffices — the map gives lookup but no ordering; the list gives ordering but O(n) lookup. The map storing node references is what makes the splice O(1).
• get: map lookup -> unlink the node -> push to head -> return value.
• put: if present, update value and move to head. If absent, create a node at the head and insert into the map; if size > capacity, drop the tail node and delete its key from the map.
• The list must be doubly linked: unlinking a node in O(1) requires its predecessor, which a singly linked list cannot give you.
• Sentinel head/tail dummy nodes remove nearly every null check from the splice logic — worth doing, and worth mentioning.

Discussion points

• Eviction must delete from both structures. Forgetting the map delete is the classic leak: the list shrinks but the map grows unbounded.
• Concurrency: the naive fix is one global lock, which serializes every read and makes the cache a bottleneck. Discuss sharding into N independently locked segments, or a concurrent map plus approximate recency (as real caches do) — exact LRU ordering is inherently a contention point.
• Trade-off vs. LFU: LRU is cheap and handles recency-skewed access well but is destroyed by a full scan that evicts the whole working set. LFU resists scans but needs frequency counters with aging, or it ossifies around historically hot keys.
• Alternatives worth naming: a language-provided linked hash map with access-order gives this almost free; segmented LRU and clock/second-chance approximate it more cheaply.
• Edge cases: capacity 0 or 1, put on an existing key at full capacity (must not evict), and whether get on a miss should count as an access.
• Extension: per-entry TTL, which adds lazy expiry on read or a background sweeper, and interacts with eviction order.