146. LRU Cache
mediumAsked at PinterestPinterest asks LRU Cache because their feed-serving infrastructure relies on bounded-memory caches for hot pins. The interviewer wants to see you reach for the doubly-linked-list + hash map combo and explain why neither data structure alone gives O(1) for both get and put.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Pinterest loops.
- Glassdoor (2026-Q1)— Recurring Pinterest data-structure design round question for L4/L5 onsite.
- LeetCode Pinterest tag (2026-Q1)— Listed as a high-frequency Pinterest question on the company-tagged problem list.
- Blind (2025-12)— Multiple Pinterest onsite reports mention LRU as the system-design / data-structures round.
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value), both in O(1) average time complexity. The cache has a fixed capacity; when full, putting a new key evicts the least recently used entry.
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 because it was least recently used at that moment.
Approaches
1. Hash map + insertion-ordered Map iteration
JavaScript's Map preserves insertion order. Delete + re-insert on get to refresh recency; iterate keys to find LRU on eviction.
- Time
- O(1) get, O(1) put amortized
- Space
- O(capacity)
class LRUCacheMap {
constructor(capacity) {
this.capacity = 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.capacity) {
const oldest = this.map.keys().next().value;
this.map.delete(oldest);
}
this.map.set(key, value);
}
}Tradeoff: Pragmatic and 15 lines if the language has insertion-ordered maps. Most interviewers count this as the optimal because the underlying complexity is the same — mention it before the linked-list version so they know you noticed the language feature.
2. Doubly linked list + hash map (canonical optimal)
Hash map from key to node pointer + doubly linked list with sentinel head/tail. Move-to-front on get/put; evict from tail when at capacity.
- Time
- O(1) get, O(1) put worst case
- Space
- O(capacity)
class Node {
constructor(key, val) {
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(0, 0); // most recent sentinel
this.tail = new Node(0, 0); // 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;
}
_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.capacity) {
const lru = this.tail.prev;
this._remove(lru);
this.map.delete(lru.key);
}
const node = new Node(key, value);
this.map.set(key, node);
this._addToFront(node);
}
}Tradeoff: The textbook answer and what Pinterest interviewers expect if they ask 'no language built-ins.' Sentinel nodes eliminate the null-check branches that break candidates under time pressure.
Pinterest-specific tips
Pinterest's data-structure design round grades on two axes: (1) you reach for both data structures together and articulate why neither alone works (hash map alone has no order; linked list alone has no O(1) lookup); (2) sentinel head/tail to eliminate edge cases. Bringing up sentinels unprompted scores higher. Mention real-world context — Pinterest's pin-serving caches are bounded LRU at every layer — without over-investing in system-design tangents.
Common mistakes
- Using a singly linked list — you need O(1) node removal, which requires a prev pointer.
- Forgetting to remove the evicted key from the hash map (memory leak).
- Off-by-one on capacity check: should evict when size >= capacity BEFORE insert, not after.
- Forgetting that put on an existing key counts as access — recency must refresh.
Follow-up questions
An interviewer at Pinterest may pivot to one of these next:
- Make it thread-safe.
- Add TTL (time-to-live) per key.
- Implement LFU (Least Frequently Used) instead.
- What if you also need O(1) for getMostRecent() and getLeastRecent() snapshots?
- Extend to a distributed LRU across N servers — how would you partition?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does Pinterest specifically care about LRU?
Pinterest's feed-serving infrastructure runs bounded-memory caches in front of every storage tier — pin metadata, board membership, user embeddings. LRU is the default eviction policy because access patterns on social-media graphs are heavy-tailed.
Will Pinterest accept the JavaScript Map shortcut?
Depends on the interviewer. Some count it as elegant; others want the linked-list version to verify you understand the underlying mechanics. Safe play: mention the Map version, then volunteer the linked-list version.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Pinterest interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →