LRU Cache is the #6 most asked LeetCode problem globally — and one of the most important system design + DSA crossover problems you'll face.
Our analysis of 10,385 verified interview questions across 259 companies shows LRU Cache appeared 116 times across 50 companies — including Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, Citadel, Cloudflare, DoorDash, LinkedIn, and MongoDB.
This problem is special: it tests your ability to design a data structure from scratch, not just apply an existing algorithm. The solution requires combining a HashMap (for O(1) lookup) with a Doubly Linked List (for O(1) insertion and deletion). Get this right and you've demonstrated real engineering intuition.
| Metric | Value |
|---|---|
| Total Interview Appearances | 116 verified mentions |
| Companies That Ask It | 50 companies |
| Global Rank | #6 out of 10,385 questions |
| Difficulty | Medium |
| Core Patterns | Design, Hash Table, Doubly Linked List |
Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, Citadel, Cloudflare, DoorDash, LinkedIn, MongoDB, Confluent, Cisco, Capital One, ByteDance, Expedia, Grab, IBM, Intel, Intuit, J.P. Morgan, Morgan Stanley, Disney, Adobe, Autodesk, Apple, Booking.com, Cruise, and 22 more.
LRU Cache is asked by infrastructure, systems, and product companies alike because caches are everywhere in real engineering — CDNs, database query caches, OS page replacement, CPU caches. Knowing how to implement one signals you understand both systems thinking and data structure design.
LeetCode #146 — LRU Cache
Design a data structure that follows the Least Recently Used (LRU) cache constraint.
Implement the LRUCache class:
LRUCache(int capacity) — Initialize with 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 or insert the key-value pair. If the number of keys exceeds capacity, evict the least recently used key.Both get and put must run in O(1) average time complexity.
LRUCache cache = new LRUCache(2); // capacity = 2
cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {1=1, 2=2}
cache.get(1); // returns 1, cache: {2=2, 1=1} (1 now most recent)
cache.put(3, 3); // evicts key 2, cache: {1=1, 3=3}
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1, cache: {3=3, 4=4}
cache.get(1); // returns -1
cache.get(3); // returns 3
cache.get(4); // returns 4The challenge: we need O(1) for three operations — lookup by key, move-to-front on access, and delete the tail (LRU) on eviction.
key → node, DLL stores nodes in recency order. HashMap gives you the node instantly; DLL lets you reorder it in O(1).To remove a node from the middle of a linked list in O(1), you need a pointer to the previous node. A singly linked list requires O(n) traversal to find the predecessor. A doubly linked list stores prev and next on every node, making removal O(1) given the node pointer.
Use two sentinel nodes — head (dummy most-recent) and tail (dummy least-recent). Real nodes sit between them.
Helper methods: remove(node) — unlinks a node from the list. insert_after_head(node) — places a node right after the head sentinel.
class Node:
def __init__(self, key=0, val=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.prev.next = node.next
node.next.prev = node.prev
def _insert_after_head(self, node):
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_after_head(node)
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_after_head(node)
if len(self.map) > self.capacity:
lru = self.tail.prev # node just before tail = LRU
self._remove(lru)
del self.map[lru.key]class LRUCache {
private class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private int capacity;
private Map<Integer, Node> map = new HashMap<>();
private Node head = new Node(0, 0); // most recent sentinel
private Node tail = new Node(0, 0); // least recent sentinel
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insertAfterHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
insertAfterHead(node);
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) remove(map.get(key));
Node node = new Node(key, value);
map.put(key, node);
insertAfterHead(node);
if (map.size() > capacity) {
Node lru = tail.prev;
remove(lru);
map.remove(lru.key);
}
}
}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();
this.head = new Node(); // most recent sentinel
this.tail = new Node(); // least recent sentinel
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_insertAfterHead(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._insertAfterHead(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._insertAfterHead(node);
if (this.map.size > this.capacity) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
}
}get and put — HashMap lookup is O(1) average. All DLL operations (remove, insert) are O(1) given node pointer.capacity nodes in the map and list at any time._remove and _insert_after_head helpers.Tag this on DSAPrep.dev under Design and Linked List.