146. LRU Cache
mediumAsked at LinearDesign a cache that evicts the least-recently-used item when it's full. Linear asks this because it's a real design problem embedded in a coding question — you need to compose a hash map and a doubly-linked list to hit O(1) get and put.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Linear loops.
- Glassdoor (2026-Q1)— Cited as a design-heavy coding problem in Linear SWE onsite reports.
- Blind (2025-11)— Multiple Linear threads list LRU Cache as a high-signal medium question testing data structure composition.
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.
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 (least recently used). After put(4,4), key 1 (not 3, since get(1) made it recent) is not evicted — key 2 was already gone, so key 3 is evicted.
Approaches
1. Ordered Map (built-in)
Use JavaScript's Map which preserves insertion order. On access, delete and re-insert to make the key 'most recent'. Evict the first key in the map (least recent).
- Time
- O(1) get and put
- 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); // move to end (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 (first key)
}
}
}Tradeoff: O(1) amortized because JS Map's delete/set and keys().next() are all O(1). A great practical answer in JavaScript. However, interviewers often want the explicit doubly-linked-list version to demonstrate understanding of the 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.
- 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 head (most recent)
this.tail = new Node(0, 0); // dummy tail (least recent)
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 reliance on language-specific Map insertion order. This is the canonical answer Linear expects when they say 'don't use built-in ordered structures.'
Linear-specific tips
Start by explaining the data structure composition before writing any code: '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 cache design.' Linear values architectural thinking. Use dummy head and tail nodes to eliminate edge cases in the linked-list operations.
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 — the map and list must stay in sync.
- Not moving the node to the front on a get() call — a cache hit counts as a recent use.
- Skipping dummy head/tail — every insert/remove then requires special-casing the empty list.
Follow-up questions
An interviewer at Linear may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item; requires tracking frequency buckets.
- How would you implement this in a thread-safe manner?
- What if capacity changes dynamically after construction?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why doubly-linked, not singly-linked?
To remove an arbitrary node in O(1), you need a pointer to its predecessor. A singly-linked list requires O(n) traversal to find it.
Why dummy head and tail?
They eliminate null-checks for inserting at the head or removing from the tail. Every operation becomes uniform pointer rewiring.
Is the JS Map approach acceptable at Linear?
Usually yes — but state upfront that you're relying on JS Map's insertion-order guarantee (per the ECMAScript spec). Then offer to implement the explicit DLL version if they prefer.
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Linear interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →