Linked List · LC #146
LRU Cache
Design an O(1) get/put LRU cache using a HashMap combined with a doubly linked list to track access order. One of the most frequently asked design+data-structure problems across all FAANG companies.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initializes the LRU cache with positive size capacity. int get(int key) returns the value of the key if it exists, otherwise returns -1. void put(int key, int value) updates the value of the key if it exists, or inserts the key-value pair. When the cache reaches its capacity, evict the least recently used key before inserting a new one. get and put must each run in O(1) average time complexity.
Sample I/O
LRUCache(2)
put(1,1) → cache {1:1}
put(2,2) → cache {1:1, 2:2}
get(1) → 1 (1 now most recent)
put(3,3) → evicts 2 → cache {1:1, 3:3}
get(2) → -1 (evicted)
put(4,4) → evicts 1 → cache {3:3, 4:4}
get(1) → -1, get(3) → 3, get(4) → 4Intuition
How to Think About It
Intuition
We need O(1) lookup (HashMap) AND O(1) ordered eviction of the least-recently-used item (a queue). A doubly linked list lets us remove any node in O(1) given a pointer to it, and a HashMap stores those pointers keyed by cache key. Together they give O(1) for both operations. The list head is most-recently-used, tail is least-recently-used.
Core Concept
Maintain a HashMap<key → node> and a doubly linked list with sentinel head and tail nodes. On get: if key exists, move its node to the front (most recent) and return value. On put: if key exists, update value and move to front; else create new node at front and add to map; if capacity exceeded, remove tail node and delete from map. Sentinel nodes eliminate null-pointer edge cases at the list ends. Time: O(1) both ops, Space: O(capacity).
When to use
Implementing any least-recently-used eviction policy; system design caching layers; OS page replacement algorithms.
When NOT to use
When LFU (Least Frequently Used) policy is needed (LC #460 - different problem). When access pattern is not temporal (e.g. priority-based eviction). When JavaScript Map insertion-order semantics suffice for a quick implementation.
Key Insights
What to Know Cold
- HashMap provides O(1) lookup; doubly linked list provides O(1) removal/insertion anywhere given a node pointer.
- Sentinel (dummy) head and tail nodes eliminate edge cases for empty list and single-element operations.
- On every access (get or put), move the node to the front - "most recently used" = front of list.
- Eviction = remove the node just before the tail sentinel - O(1) with doubly linked list.
- JavaScript/TypeScript Map preserves insertion order; delete-and-reinsert mimics the move-to-front operation without a custom DLL.
1 example
Worked Examples
Full LRU Cache with capacity 2
put(1,1), put(2,2), get(1), put(3,3) evicts 2, get(2) returns -1
HashMap + doubly linked list with sentinel nodes
class LRUCache {
private cap: number;
private cache: Map<number, number>;
constructor(capacity: number) { this.cap = capacity; this.cache = new Map(); }
get(key: number): number {
if (!this.cache.has(key)) return -1;
const val = this.cache.get(key)!;
this.cache.delete(key);
this.cache.set(key, val); // move to end (most recent)
return val;
}
put(key: number, value: number): void {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.cap)
this.cache.delete(this.cache.keys().next().value!); // evict LRU (first key)
}
}Output: get(1)→1, get(2)→-1, get(3)→3, get(4)→4
Asked at nearly every FAANG onsite - tests HashMap + DLL design, O(1) constraints, and ability to implement from scratch without built-in ordered containers.