How do you design an LRU cache with O(1) get and put?
Combine a hash map for instant lookup with an ordering of recent use. In JavaScript a Map remembers insertion order, so deleting and re-inserting a key on each access moves it to the newest end; the oldest key is evicted when full.
Explain it simply
An LRU (least recently used) cache is like the small shelf next to your study table: it holds only a few books, and when it is full you put back the book you have not touched for the longest time.
You need two things at once: find a key fast, and know which key is oldest. The classic answer is a hash map plus a doubly linked list. In JavaScript a Map already remembers insertion order, so it can do both jobs: every time you use a key, delete it and set it again so it moves to the end. The first key in the Map is then always the least recently used.
Example
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return -1;
const value = this.map.get(key);
this.map.delete(key);
this.map.set(key, value); // mark as most recent
return value;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) {
const oldest = this.map.keys().next().value;
this.map.delete(oldest);
}
}
}
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // Output: 1
cache.put(3, 3); // evicts key 2
console.log(cache.get(2)); // Output: -1
console.log(cache.get(3)); // Output: 3Complexity
get and put are O(1) on average, space O(capacity).
What to say in the interview
"I need O(1) lookup and O(1) reordering, so the textbook design is a hash map pointing into a doubly linked list. In JavaScript a Map keeps insertion order, so I delete and re-set a key on every access and evict the first key when over capacity. Both get and put are O(1) on average."
Common mistakes
- Forgetting to refresh recency on get, not only on put.
- Using an array and splice for ordering, which makes operations O(n).