146. LRU Cache
mediumAsked at DRWDRW uses LRU Cache because low-latency market-data systems rely on exactly this design: a bounded cache of recently-seen instrument snapshots, where the stale entry is evicted on each new quote. O(1) get and put are non-negotiable — the interviewer will ask for the doubly-linked-list proof.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DRW loops.
- Glassdoor (2026-Q1)— DRW SWE onsite candidates consistently cite LRU Cache as one of the highest-signal medium problems, with interviewers expecting the explicit doubly-linked-list implementation.
- Blind (2025-11)— DRW threads note that interviewers follow up the LRU Cache solution with questions about concurrent access and thread-safe eviction.
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity) initializes the LRU cache with a positive size capacity. int get(int key) returns the value of the key if it exists, otherwise -1. void put(int key, int value) updates the value if the key exists, otherwise inserts the key-value pair. When the number of keys exceeds the capacity, evict the least recently used key.
Constraints
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5At most 2 * 10^5 calls will be made to get and put.
Examples
Example 1
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)[null,null,null,1,null,-1,null,1,3,4]Explanation: After put(3,3), key 2 is evicted (LRU). After put(4,4), key 3 is evicted.
Approaches
1. Ordered Map (JS built-in)
Use JavaScript's Map which preserves insertion order. On access, delete and re-insert to move the key to the 'most recent' position. Evict the first key (least recent).
- Time
- O(1) amortized get and put
- Space
- O(capacity)
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
this.cache.delete(this.cache.keys().next().value);
}
}
}Tradeoff: O(1) amortized in JS. Mention that this relies on the ECMAScript insertion-order guarantee for Map. DRW will ask for the explicit DLL version to confirm you understand the underlying data structure.
2. Hash map + doubly-linked list (canonical)
A Map gives O(1) key lookup; a doubly-linked list gives O(1) move-to-front and evict-from-tail. Dummy head (most recent) and tail (least recent) nodes eliminate edge-case handling.
- Time
- O(1) get and put
- Space
- O(capacity)
class Node {
constructor(key, val) { this.key = key; this.val = val; this.prev = this.next = null; }
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new Node(0, 0); // dummy head (most recent)
this.tail = new Node(0, 0); // dummy tail (least recent)
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._insertFront(node); this.map.set(key, node);
if (this.map.size > this.capacity) {
const lru = this.tail.prev;
this._remove(lru); this.map.delete(lru.key);
}
}
}Tradeoff: Strict O(1) for all operations. This is the canonical DRW answer — they want to see you implement _remove and _insertFront explicitly, proving you understand pointer rewiring.
DRW-specific tips
DRW will ask: 'How does this design change for a thread-safe cache under concurrent reads and writes?' Answer: a read-write lock (shared for reads, exclusive for writes) protects the Map and DLL. For very high contention, a segmented LRU (split into multiple independent shards, each with its own lock) reduces lock contention by a factor of the shard count. They may also ask: 'What if eviction policy switches from LRU to LFU mid-operation?' — that is LC 460.
Common mistakes
- Using a singly-linked list — O(n) removal without a pointer to the predecessor.
- Forgetting to delete the evicted node's key from the Map — Map and list must stay in sync.
- Not moving the node to the front on a get() — a cache hit counts as a recent access.
- Skipping dummy head/tail — every insert/remove then requires null-checks for the empty-list case.
Follow-up questions
An interviewer at DRW may pivot to one of these next:
- LFU Cache (LC 460) — evict by least-frequently-used; requires frequency buckets.
- Thread-safe LRU — how would you protect get and put under concurrent access?
- How would you shard an LRU cache across multiple CPU cores to reduce contention?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked and not singly-linked?
To remove an arbitrary node in O(1), you need a pointer to its predecessor. A singly-linked list requires O(n) traversal.
Why dummy head and tail?
They eliminate null checks: every insertFront and remove uses the same four-pointer rewire pattern regardless of the list's fullness.
How does DRW use LRU caches in production?
Market-data snapshot caches — e.g., the most recent quote for each of 3,000 instruments — are bounded by memory. The LRU policy evicts the least-recently-quoted instrument, ensuring the hot instruments always stay in cache.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →