146. LRU Cache
mediumAsked at ShopifyLRU Cache is Shopify's canonical 'design a data structure' round. Storefronts have heavy cache eviction needs (product pages, theme assets, session tokens), so the interviewer is grading whether you reach for the doubly-linked-list + hash-map combo and explain why neither alone gives O(1) get + put.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Shopify loops.
- Glassdoor (2026-Q1)— Shopify Senior Backend Developer + Engineering Lead onsites repeatedly include LRU Cache as the data-structure-design round.
- Blind (2025-12)— Shopify Senior+ Backend offers report LRU as the standard data-structure round, often with a TTL follow-up.
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.
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) the cache is full so key 2 (least recently used) is evicted.
Approaches
1. Hash map with insertion-ordered Map
JavaScript Map preserves insertion order. Delete + re-insert on get to refresh recency; iterate Map.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: Ships in 15 lines. Same O(1) amortized complexity as the doubly-linked-list version, just leaning on a language feature. Most Shopify interviewers accept this if you also mention the underlying data structure.
2. Doubly linked list + hash map (canonical)
Hash map from key to node pointer + doubly linked list with sentinel head/tail. Move-to-front on every get/put.
- 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);
this.tail = new Node(0, 0);
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. Sentinel head/tail nodes eliminate the null-pointer checks that break candidates under time pressure. Worst-case O(1) per operation (the Map version is amortized only because Map's iteration can be implementation-dependent).
Shopify-specific tips
Shopify's expected follow-ups: (1) add TTL per key, (2) make it thread-safe (talk about a mutex around mutations, or sharded caches), (3) what if the workload is read-heavy and write-rare (mention W-TinyLFU or 2Q). Senior candidates are also asked to wire this behind an HTTP cache layer — be ready to discuss cache invalidation triggers (publish events, webhook callbacks).
Common mistakes
- Using a singly linked list — you need O(1) node removal, which requires prev pointers.
- Forgetting to delete the evicted key from the hash map (causes a memory leak that only surfaces under load).
- Off-by-one on capacity: evict when size >= capacity BEFORE inserting, not after.
- Forgetting that put on an existing key counts as access — recency must refresh, value must overwrite.
- Storing values instead of node references in the map — eviction then becomes O(n).
Follow-up questions
An interviewer at Shopify may pivot to one of these next:
- Add TTL (time-to-live) per key with lazy expiration.
- Make it thread-safe.
- Implement LFU (Least Frequently Used) instead — LeetCode 460.
- What if you also need O(1) for getMostRecent() and getLeastRecent() snapshots?
- Distributed LRU across multiple cache nodes — consistent hashing.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Will Shopify accept the JavaScript Map shortcut?
Most interviewers accept it if you explicitly call out the underlying data structures (hash map + insertion-ordered linked list inside V8's Map implementation). Safer move: write the Map version first, then offer to expand to the explicit doubly-linked-list version if asked.
Why sentinel head/tail nodes?
They eliminate the need to special-case insert-at-empty or remove-the-only-node. Every real node always has a non-null prev and next, so _remove and _addToFront become four unconditional pointer assignments. Robustness under time pressure.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Shopify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →