146. LRU Cache
mediumAsked at GleanGlean uses LRU Cache to test data structure composition — the same hash map + doubly-linked list pattern that sits at the heart of their real-time document caching layer, where recently accessed enterprise content must be served with sub-millisecond latency.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Glean loops.
- Glassdoor (2026-Q1)— LRU Cache is cited as a signature Glean onsite problem due to its direct relevance to their caching infrastructure.
- Blind (2025-12)— Glean SWE candidates consistently list LRU Cache as a high-frequency medium asked in both the coding and system-design-lite rounds.
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 get and put must run 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), key 2 is evicted. After put(4,4), key 3 is evicted (key 1 was recently accessed via get(1)).
Approaches
1. JS Map (insertion-order exploitation)
JavaScript's Map preserves insertion order. On every access, delete and re-insert the key to move it to the 'most recent' end. Evict by deleting the first key (least recent).
- 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: Leverages JS Map's ECMAScript-specified insertion order. Practical for JavaScript interviews, but interviewers often ask for the explicit doubly-linked-list version to prove understanding of the underlying data structure.
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 references.
- 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: Explicit O(1) for all operations with no language-specific assumptions. This is what Glean interviewers typically want to see — it proves you understand the data structure, not just the API.
Glean-specific tips
Open with the design explanation before any code: 'I need O(1) lookup — hash map. I need O(1) move-to-front and O(1) eviction — doubly-linked list. Together they give me the LRU cache.' Glean's engineering culture values thinking-out-loud system design. Use dummy head and tail sentinels — they eliminate all edge cases in pointer rewiring. Mention the real-world connection: enterprise search caches recently accessed document metadata exactly this way.
Common mistakes
- Using a singly-linked list — removing an arbitrary node is O(n) without a back pointer.
- Forgetting to remove the evicted node from the Map — map and list must stay in sync.
- Not moving the node to the front on get() — a cache hit is a recent use.
- Storing the value in the Map instead of a node reference — you need the node pointer to do O(1) list operations.
Follow-up questions
An interviewer at Glean may pivot to one of these next:
- LFU Cache (LC 460) — evict the least-frequently-used item; requires frequency buckets.
- How would you make this thread-safe for concurrent access?
- Design a distributed LRU cache across multiple machines — how does eviction policy change?
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 store the key inside the Node?
When evicting the LRU node (tail.prev), you must delete the corresponding entry from the Map. Without the key stored in the node, you have no way to find that map entry in O(1).
Practice these live with InterviewChamp.AI
Drill LRU Cache and other Glean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →