146. LRU Cache
mediumAsked at GustoDesign a cache that evicts the least-recently-used item when it's full. Gusto asks this because caching is real infrastructure in their payroll platform — they want to see the hash map + doubly-linked list composition and hear you explain why each data structure is needed before writing any code.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Gusto loops.
- Glassdoor (2026-Q1)— Cited in Gusto senior SWE onsite reports as a design-heavy coding problem testing data-structure composition.
- Blind (2025-11)— Gusto interview threads list LRU Cache as a high-signal medium question for senior candidates with a follow-up on LFU Cache.
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity) initializes the 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, or 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. get(2) returns −1 since 2 was evicted.
Approaches
1. JS Map (insertion-order trick)
JavaScript's Map preserves insertion order. Delete and re-insert a key on access to mark it as most recent. Evict the first key in the map when capacity is exceeded.
- Time
- O(1) get and put (amortised)
- 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); // re-insert = move to most-recent
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); // evict LRU
}
}
}Tradeoff: Elegant and idiomatic in JS. Relies on the ECMAScript Map insertion-order guarantee. Mention this dependency explicitly — interviewers may ask you to implement it without relying on Map ordering.
2. Hash map + doubly-linked list (canonical)
A Map gives O(1) key lookup. A doubly-linked list with dummy head and tail gives O(1) move-to-front and eviction. The map stores key → node.
- 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 — most recent side
this.tail = new Node(0, 0); // dummy — least recent side
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: Explicit O(1) for all operations, no language-specific ordering assumptions. This is what Gusto expects when they say 'implement it from scratch.'
Gusto-specific tips
Gusto interviewers want the architecture justification first: 'I need O(1) lookup — that's a hash map. I need O(1) move-to-front and eviction — that's a doubly-linked list. Combining them is the canonical LRU design.' Use dummy head and tail nodes to avoid all edge-case null checks. Gusto may also ask 'how would you test this?' — walk through a put-get-evict sequence step by step.
Common mistakes
- Using a singly-linked list — you can't remove a node in O(1) without a pointer to its predecessor.
- Forgetting to delete the evicted node from the map — map and list fall out of sync.
- Not moving the node to the front on get() — a cache hit counts as a recent use.
- Skipping dummy sentinel nodes — every insert/remove then requires special null-checking.
Follow-up questions
An interviewer at Gusto may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item, breaking ties by recency.
- How would you make this thread-safe for concurrent access?
- What if you needed to support a time-based expiry (TTL) per entry?
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. Singly-linked requires O(n) traversal to find it.
Why store the key in the node?
When evicting the LRU node from the tail, you need its key to delete it from the map. The node must carry the key.
Is the JS Map approach acceptable at Gusto?
Yes — but state that you're relying on ES6 Map's insertion-order guarantee and offer the explicit doubly-linked-list version if they want language-agnostic code.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Gusto interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →