Design a data structure with two operations:
get(key)— return the value if the key exists, else -1.put(key, value)— insert or update the key with the given value.
The structure has a fixed capacity. When inserting causes the structure to exceed capacity, evict the least recently used (LRU) entry. Both operations must run in O(1) time.
This is LeetCode 146, “LRU Cache”, and it is the gateway drug to system design in the modern interview canon. The problem is small enough to code in 20 minutes, but it forces the candidate to think about data structures and access patterns together — exactly the integrated thinking that system design interviews demand. The cultural status of LRU cache is somewhere between “coding question” and “system design question”; in 2026 it is asked at both phone screens (as a coding question) and onsites (as a warmup design question).
The naive approaches and why they fail
- Just a hash map. O(1) get and put, but no notion of “least recently used”. Cannot evict correctly.
- Hash map + recency timestamps. When evicting, scan all entries to find the smallest timestamp. O(1) get/put but O(n) eviction. Fails the O(1) requirement.
- Hash map + sorted structure (TreeMap, sorted array). O(log n) for the recency update on each access. Fails the O(1) requirement.
- Linked list only. O(1) eviction (just remove head), but O(n) lookup. Fails O(1) get.
None of these works. The optimal data structure is a hash map plus a doubly-linked list, with each hash map entry pointing to a node in the list. The list orders entries by recency; the hash map gives O(1) lookup. Updating recency is O(1) — find the node via hash map, remove it from its current position, insert at the front.
The optimal design
class Node:
def __init__(self, key, val):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {} # key -> Node
# Sentinel head and tail
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
elif len(self.cache) >= self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = Node(key, value)
self._add_to_front(node)
self.cache[key] = node
O(1) for both get and put. The doubly-linked list with sentinel nodes keeps insertion and removal O(1) regardless of position. The hash map provides O(1) lookup.
Why sentinel nodes
The sentinel head and tail nodes simplify the linked list operations. Without sentinels, every insertion and removal has to handle the “is this the head or tail” edge case explicitly. With sentinels, every real node has both a previous and next pointer, and the operations are uniform.
This is a common pattern in linked list code; the boilerplate of two extra nodes pays off in cleaner inner-loop code.
Why this question is famous
LRU Cache earned its place in the canon for three reasons:
- The data-structure-combination insight. Most LeetCode problems use one data structure. This one needs two, working together. Recognizing that the right answer is “hash map + doubly-linked list” is exactly the kind of insight system design rounds test for.
- The real-world relevance. LRU caches are everywhere — CDNs, page replacement in operating systems, query caches in databases, key-value caches in distributed systems. Facebook’s TAO (their cache layer in front of their social graph database) uses LRU at scale. The problem is not artificial; it is the same problem that real engineers solve.
- The bridge to system design. The 20-minute version is a coding problem. The 60-minute version is “design a distributed cache with LRU eviction” — a full system design round. The same problem extends from junior to staff interview level.
Variations interviewers ask
- LFU Cache (LC 460). Least Frequently Used eviction. Harder; requires a frequency counter and grouped structure. Often asked as a follow-up.
- Cache with TTL. Entries expire after a time. Adds a min-heap or sorted structure for expiry tracking.
- Distributed LRU. Now you have multiple nodes; how do you maintain LRU across them? Becomes a system design question.
- Write-through vs write-back. The cache sits in front of a slower store; how do you handle writes? Same as the SD round on caching strategies.
- Concurrent LRU. Multiple threads accessing the cache. Needs locking. Sometimes the locking is the entire interview.
The Facebook TAO connection
Facebook’s TAO (The Associations and Objects) is the company’s social graph cache layer. It sits in front of MySQL and serves billions of reads per second by caching recently-accessed graph data in memory. The eviction policy is LRU at the leaf level. Engineers who interviewed at Meta in the late 2010s and early 2020s often described their system design rounds as essentially “rediscover TAO from first principles” — and the LRU cache problem is the smallest version of that journey.
Other real-world LRU caches: Memcached (supports LRU), Redis (supports several eviction policies including LRU and approximate LRU), the Linux kernel’s page replacement (uses an approximation of LRU), CDN edge caches at Cloudflare and Akamai (LRU and variants).
What interviewers grade
This is a phone-screen-tier coding question (medium) or a junior-level system design warmup. Signal layers:
- Recognize the data structure combination. The candidate articulates that one data structure is insufficient.
- Choose hash map + doubly-linked list. Stating the choice is the key insight.
- Implement cleanly. Including sentinels, removing duplicate code in
getandput. - State complexity. O(1) for both operations, with hash map and linked list cooperating.
- Discuss real-world considerations. Concurrency, expiry, write-through. A polished candidate volunteers some of these unprompted.
Is it asked in 2026?
Yes, ubiquitously. LRU Cache is one of the most-asked phone-screen questions across FAANG, tier-2 tech, and fintech. It also appears as a warmup in senior+ system design rounds, where the interviewer expects the candidate to explain LRU at the data-structure level before extending it to a distributed setting. The question has not aged out because the underlying skill (combining data structures, thinking about real-world cache behavior) is permanently relevant.
Frequently Asked Questions
What is the time complexity?
O(1) for both get and put. The hash map provides O(1) lookup; the doubly-linked list provides O(1) insertion and removal at any position; the combination provides O(1) recency updates.
Why a doubly-linked list and not a singly-linked list?
Doubly-linked allows O(1) removal of a node when you have a reference to it. With a singly-linked list, removing a node requires traversing to find its predecessor — O(n).
What is the difference between LRU and LFU?
LRU evicts the entry that was used least recently. LFU evicts the entry that has been used least frequently overall. LFU requires more bookkeeping (frequency counts) but is sometimes a better policy for workloads with stable access frequencies.
Are real-world caches strict LRU?
Often no. Strict LRU requires updating the doubly-linked list on every read, which is expensive at high scale. Real systems use approximations like clock replacement or 2Q. The interview version is the strict LRU; the production version is usually an approximation.
Is this problem still asked in 2026?
Yes, ubiquitously. It is one of the most-asked phone screen questions and a standard warmup in senior+ system design rounds.