LRU Cache — The Classic O(1) Design Problem Every Senior Engineer Must Know

Problem Statement

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy.

Implement the LRUCache class:

LRUCache(int capacity) — Initialize the LRU cache with a positive size capacity.
int get(int key) — Return the value of the key if it exists, otherwise return -1.
void put(int key, int value) — Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Constraints:

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Example:
Input:
  ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  [[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]]
Output:
  [null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation:
  LRUCache(2) — capacity = 2
  put(1,1)    — cache: {1:1}
  put(2,2)    — cache: {1:1, 2:2}
  get(1)      — returns 1; 1 is now most recently used
  put(3,3)    — evicts 2 (LRU); cache: {1:1, 3:3}
  get(2)      — returns -1 (evicted)
  put(4,4)    — evicts 1 (LRU); cache: {3:3, 4:4}
  get(1)      — returns -1 (evicted)
  get(3)      — returns 3
  get(4)      — returns 4

Why This Problem Matters

LRU Cache is the most important data structure design problem in technical interviews. It combines two fundamental data structures — a HashMap and a doubly linked list — in a non-obvious way to achieve O(1) for all operations. Amazon, Google, Meta, and Microsoft include this problem in senior-level interviews because it tests your understanding of how data structures interact at a systems level, not just as standalone components.

In the real world, LRU caches are ubiquitous: CPU instruction caches, browser page caches, database buffer pools, CDN edge caches, and DNS resolver caches all use LRU or LRU-like eviction policies. When a candidate can design and implement LRU from scratch, it signals that they understand cache semantics at the implementation level — a prerequisite for reasoning about performance in distributed systems.

The problem is also a litmus test for design clarity. A candidate who immediately reaches for OrderedDict in Python (a valid shortcut) shows library familiarity. A candidate who implements the doubly linked list from scratch shows that they understand why the design works. In a senior interview, you will be asked to explain the DLL design, and the follow-up will probe whether you can extend it to LFU (Least Frequently Used) cache — which requires substantially different data structures.

The core challenge: a HashMap gives O(1) key lookup but no ordering. A doubly linked list gives O(1) insert/delete at known positions but no fast lookup. Together, they provide O(1) for both lookup and order management. This combination — a map to a DLL node — is one of the most elegant compound data structures in computer science.

The Core Insight

The LRU policy requires two operations:

O(1) lookup: Given a key, return its value.
O(1) eviction: When at capacity, remove the least recently used item.

The insight: use a doubly linked list to maintain access order (most recent at head, least recent at tail), and a HashMap from key to DLL node for O(1) access to any specific node.

When a key is accessed (get) or updated (put):

Move the corresponding DLL node to the head of the list.

When capacity is exceeded (put of a new key):

Remove the node at the tail of the list (the LRU item).
Delete its key from the HashMap.

Use dummy head and tail sentinel nodes to simplify edge cases — they eliminate the need to handle null-pointer edge cases for empty-list insertions and removals.

The HashMap stores key → node pointer. Each node stores key, value, prev, next. The key in the node is needed for the eviction step: when you remove the tail node, you need its key to delete it from the HashMap.

Visual Dry Run

Capacity = 2. Operations: put(1,1), put(2,2), get(1), put(3,3), get(2)

After put(1,1):  H ↔ [1:1] ↔ T      map: {1→node1}
After put(2,2):  H ↔ [2:2] ↔ [1:1] ↔ T   map: {1→node1, 2→node2}
After get(1):    H ↔ [1:1] ↔ [2:2] ↔ T   map: {1→node1, 2→node2}
                 (1 moved to head — it's now most recent)
put(3,3) — capacity exceeded:
  Evict tail.prev = node2 (key=2)
  Remove from map: del map[2]
  Remove from DLL: H ↔ [1:1] ↔ T
  Insert 3 at head: H ↔ [3:3] ↔ [1:1] ↔ T
  map: {1→node1, 3→node3}
get(2) → -1 (evicted)

Solution (Optimal)

class Node:
    """Doubly linked list node storing key and value."""
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
 
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key → Node
 
        # Sentinel head (most recent) and tail (least recent)
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node: Node) -> None:
        """Remove a node from the doubly linked list."""
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _insert_front(self, node: Node) -> None:
        """Insert a node right after the head (most recently used position)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._insert_front(node)  # Mark as most recently used
        return node.val
 
    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._insert_front(node)
 
        if len(self.map) > self.capacity:
            # Evict the least recently used (node before tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
 
 
# Python shortcut using OrderedDict
from collections import OrderedDict
 
class LRUCache_OrderedDict:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()  # Maintains insertion/access order
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark as most recently used
        return self.cache[key]
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Evict least recently used

class Node {
    constructor(key = 0, val = 0) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}
 
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map();
 
        // Sentinel nodes
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
 
    _remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    _insertFront(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }
 
    get(key) {
        if (!this.map.has(key)) return -1;
        const node = this.map.get(key);
        this._remove(node);
        this._insertFront(node);
        return node.val;
    }
 
    put(key, value) {
        if (this.map.has(key)) {
            this._remove(this.map.get(key));
        }
        const node = new Node(key, value);
        this.map.set(key, node);
        this._insertFront(node);
 
        if (this.map.size > this.capacity) {
            const lru = this.tail.prev;
            this._remove(lru);
            this.map.delete(lru.key);
        }
    }
}

Complexity Analysis

Operation	Time	Space
get	O(1)	—
put	O(1)	—
Overall space	—	O(capacity)

Both get and put are O(1) because HashMap lookups and DLL node insertions/removals at known positions are O(1).

Common Mistakes

Using a singly linked list instead of a doubly linked list. A singly linked list cannot remove a node in O(1) without knowing the previous node. A doubly linked list gives direct access to node.prev, enabling O(1) removal.
Forgetting to store the key in each DLL node. When you evict the tail, you need to know which key to delete from the HashMap. Without the key in the node, you would need a reverse lookup.
Not using sentinel (dummy) head and tail nodes. Without sentinels, every insertion and deletion requires null-pointer checks that add code complexity and bug surface. Sentinels make the code uniform.
Forgetting to update the DLL on put for an existing key. If the key already exists and you only update the value without moving the node to the front, the node's LRU position is wrong.
Using Python's regular dict (ordered by insertion in Python 3.7+) instead of OrderedDict. Regular dict preserves insertion order but does not support move_to_end, making access-order tracking impossible without extra bookkeeping.

Follow-up Questions

How would you extend this to LFU (Least Frequently Used) cache? LFU requires tracking access frequency in addition to recency. Use a HashMap from key to (value, frequency), a HashMap from frequency to a doubly linked list of keys at that frequency, and a variable tracking the minimum frequency. All operations remain O(1). This is LC 460.

What if you need a time-aware LRU (evict entries older than T seconds)? Add a timestamp to each node. On access, check the timestamp difference against T. On eviction, walk from the tail and remove all nodes older than T before applying the standard LRU eviction.

How would you make this thread-safe? Wrap all operations with a mutex (lock). For higher concurrency, use lock striping — partition the cache into segments, each with its own lock — similar to Java's ConcurrentHashMap.

What is the real-world difference between LRU and LFU? LRU evicts the least recently accessed item. LFU evicts the least frequently accessed item. LRU is simple but vulnerable to cache thrashing (one access of a cold item evicts a warm item). LFU is more resilient but harder to implement. Many production systems use a variant like "LIRS" or "W-TinyLFU" that combines both.

Could you implement LRU with a sorted set instead of a DLL? A sorted set (balanced BST) keyed by timestamp gives O(log n) per operation. This is worse than O(1) but simpler to implement and more flexible (supports range queries). Redis uses a sorted set for its LRU approximation.

Key Takeaways

LC 146 LRU Cache requires O(1) get and put — only a hashmap-plus-doubly-linked-list (or OrderedDict) achieves this.
The hashmap maps key to node; the DLL maintains recency order; together they give O(1) for every operation.
On get, move the node to the front (most-recent end). On put over an existing key, update value and move to front.
On put when at capacity, remove the tail node and delete its key from the hashmap before inserting the new entry.
Use sentinel head and tail nodes to avoid edge-case branches when the list is empty or has one element.
Python's collections.OrderedDict (or move_to_end/popitem(last=False)) is the idiomatic shortcut interviewers accept.
LRU is foundational for OS page replacement, CPU/L2 caches, Redis maxmemory-policy, and CDN edge caches.

LC 146 — LRU Cache: This problem.
LC 460 — LFU Cache: More complex variant using frequency-ordered linked lists.
LC 432 — All O'one Data Structure: Maintain O(1) increment/decrement of string counts and O(1) max/min retrieval.
LC 716 — Max Stack: Design a stack that supports O(1) popMax — similar compound data structure thinking.
LC 355 — Design Twitter: Design a feed that shows the 10 most recent tweets — uses a merge of linked lists.
LC 1146 — Snapshot Array: Design a versioned array — related compound data structure design problem.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Follow-up Questions#

Key Takeaways#

Related Problems#

Related reading