146. LRU Cache
mediumAsked at HubSpotHubSpot asks LRU Cache because it's a real design problem embedded in a coding question — their platform caches CRM data aggressively, and engineers are expected to understand how eviction policies are implemented, not just configured.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in HubSpot loops.
- Glassdoor (2026-Q1)— HubSpot SWE onsite reports list LRU Cache as a high-signal medium problem testing data structure composition.
- Blind (2025-12)— Multiple HubSpot interview threads cite LRU Cache as a canonical design-in-coding question.
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. Both operations must run in O(1) average time.
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 get(1), key 1 becomes most recent. After put(4,4), key 3 (now LRU) is evicted.
Approaches
1. JavaScript Map (insertion-order)
JS Map preserves insertion order. On access, delete and re-insert the key to move it to 'most recent'. Evict by deleting the first key (least recently used) when over capacity.
- Time
- O(1) amortized
- 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: Elegant JavaScript-specific solution leveraging Map's insertion-order guarantee (per ECMAScript spec). State this dependency explicitly. Interviewers may ask for the explicit doubly-linked-list version to prove 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. The map stores key → node pointers. Dummy head (MRU side) and tail (LRU side) eliminate edge cases.
- 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 MRU sentinel
this.tail = new Node(0, 0); // dummy LRU sentinel
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: Language-agnostic, explicit O(1) for all operations. This is the canonical answer HubSpot expects when they say 'implement without relying on ordered map internals.' The node must store the key so the map can be updated on eviction.
HubSpot-specific tips
Verbalize the data structure composition first: 'I need O(1) lookup — hash map. I need O(1) move-to-front and eviction — doubly-linked list. Combining them is the textbook LRU design.' HubSpot values architectural thinking before code. Use dummy sentinels at head and tail to eliminate edge cases. Always store the key in the node — eviction requires deleting from the map using that key.
Common mistakes
- Using a singly-linked list — 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 drift out of sync.
- Not moving the node on get() — a cache hit counts as a recent use and must update recency.
- Skipping dummy head/tail — every insert/remove then requires special-casing empty list.
Follow-up questions
An interviewer at HubSpot may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item; needs frequency buckets.
- How would you make the LRU cache thread-safe?
- What if capacity can change dynamically after construction?
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.
Why dummy head and tail?
They eliminate null-checks for inserting at the front or removing from the end. Every operation becomes uniform pointer rewiring.
Why does the node store the key?
When you evict the LRU node (tail.prev), you also need to delete it from the map. Without the key in the node, you can't find which map entry to remove.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other HubSpot interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →