146. LRU Cache
mediumAsked at UberDesign an LRU (Least Recently Used) cache supporting get and put in O(1). Uber asks this to test whether you can combine a hash map with a doubly linked list and explain why neither structure alone suffices.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Uber loops.
- Glassdoor (2026-Q1)— Uber L4/L5 onsite reports consistently include LRU Cache as a design-heavy medium.
- Blind (2025-12)— Recurring in Uber backend platform onsite reports.
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity), int get(int key), void put(int key, int value). Both operations must run in O(1) average time complexity.
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: put(3,3) evicts key 2 (LRU). put(4,4) evicts key 1. So get(2)=-1, get(1)=-1, get(3)=3, get(4)=4.
Approaches
1. Map with order array
Store values in a map; track recency in an array. On any access, move the key to the end of the array.
- Time
- O(n) per op (array splice)
- Space
- O(n)
class LRUCacheNaive {
constructor(capacity) { this.cap = capacity; this.map = new Map(); this.order = []; }
get(key) {
if (!this.map.has(key)) return -1;
this.order.splice(this.order.indexOf(key), 1);
this.order.push(key);
return this.map.get(key);
}
put(key, value) {
if (this.map.has(key)) this.order.splice(this.order.indexOf(key), 1);
else if (this.map.size >= this.cap) { const lru = this.order.shift(); this.map.delete(lru); }
this.map.set(key, value);
this.order.push(key);
}
}Tradeoff: Easy to reason about but misses the O(1) requirement. Mention as a stepping stone before pivoting.
2. Hash map + doubly linked list (optimal)
Map key -> node. Doubly linked list orders by recency, with dummy head (MRU side) and tail (LRU side). Get/put unlinks and re-inserts at head in O(1).
- Time
- O(1) per op
- Space
- O(capacity)
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map();
this.head = { key: null, val: null, prev: null, next: null };
this.tail = { key: null, val: null, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToFront(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._addToFront(node);
return node.val;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.val = value;
this._remove(node);
this._addToFront(node);
return;
}
if (this.map.size >= this.cap) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
const node = { key, val: value, prev: null, next: null };
this._addToFront(node);
this.map.set(key, node);
}
}Tradeoff: True O(1). The map gives O(1) lookup; the doubly linked list gives O(1) reorder. Neither alone suffices.
3. JavaScript Map insertion-order trick
JS Map preserves insertion order. Delete-then-set moves a key to the back; the front is the LRU.
- Time
- O(1) per op
- Space
- O(capacity)
class LRUCacheJS {
constructor(capacity) { this.cap = capacity; this.map = new Map(); }
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key);
this.map.set(key, val);
return val;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.cap) {
const oldest = this.map.keys().next().value;
this.map.delete(oldest);
}
this.map.set(key, value);
}
}Tradeoff: Cleanest code but only acceptable if you state the language-specific assumption. Uber interviewers generally expect the explicit doubly-linked-list version because it demonstrates the underlying data-structure understanding.
Uber-specific tips
Uber's bar on this is articulating why you need both a map and a linked list. Say: 'I need O(1) lookup (so a hash map) and O(1) reorder (so a doubly linked list). The map points into the list. On every get/put I unlink the node and re-link at the head.' Coding the JS-Map version without naming the explicit DLL/map combo is fine for senior+ but loses signal at L4.
Common mistakes
- Singly linked list — can't unlink in O(1) without the prev pointer.
- Forgetting to delete the evicted key from the map.
- Not storing the key in the node — required so the eviction step knows which map entry to remove.
Follow-up questions
An interviewer at Uber may pivot to one of these next:
- LFU Cache (LC 460) — frequency-aware, harder.
- What if the cache is shared across threads? (Locking, sharded, etc.)
- What if get and put had different time bounds? (Could relax DLL to a list with periodic compaction.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly linked, not singly?
On eviction, you need to remove the tail in O(1). Singly linked would require finding the prev of the tail in O(n).
Is the JS-Map trick acceptable in interview?
Yes, if you call it out: 'JavaScript Map preserves insertion order, so I can use delete-then-set to move keys to the back.' Without naming the assumption, it looks like you got lucky.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Uber interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →