LRU Cache
Build an LRUCache class that holds a fixed number of entries and, once full, throws away whichever entry was used least recently.
new LRUCache(capacity)— how many entries fit before eviction starts.get(key)— returns the value, or-1if the key is not there. A successful get counts as a use.put(key, value)— inserts or updates. Counts as a use either way. If this takes the cache past its capacity, evict the least recently used entry.
Both get and put must run in O(1) — no scanning the keys to find the oldest one.
Examples
const cache = new LRUCache(3);
cache.put('user:1', { name: 'Pratik' });
cache.put('user:2', { name: 'Rahul' });
cache.put('user:3', { name: 'Aman' });
cache.get('user:1'); // { name: 'Pratik' }
cache.put('user:4', { name: 'Vikas' }); // over capacity
cache.get('user:2');
cache.get('user:1');-1
{ name: 'Pratik' }Constraints
- 1 <= capacity <= 1000
- Keys are strings; values can be anything, including falsy values
- get and put must both be O(1)
Notes
- A read is a use. Forgetting that get refreshes recency is the single most common mistake here.
- Storing a miss — even as -1 — quietly consumes capacity and evicts real entries early.
- The test suite grades behaviour, not complexity. O(1) is still a requirement, and the Solution tab explains how to get it.
Source
Hints
Editorial: LRU Cache
Two questions, one structure
An LRU cache has to answer two things instantly: what is the value for this key, and which key was used longest ago. A plain object answers the first in O(1) and the second not at all — you would have to scan.
The classic answer is a hash map paired with a doubly linked list: the map gives O(1) lookup, the list gives O(1) reordering, and each map entry points at its node. In JavaScript there is a shortcut, because Map already is that pairing.
Approach
A Map iterates in insertion order, so its first key is the oldest and map.keys().next().value reaches it without a scan. Marking something as used is then delete-then-set, which moves it to the end.
Implementation
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); // Delete then re-set to move it to the newest position. this.map.delete(key); this.map.set(key, value); 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) { // The first key in iteration order is the oldest. const oldest = this.map.keys().next().value; this.map.delete(oldest); } } }
Worth knowing
A read is a use. This is the mistake almost everyone makes first. get has to reorder as well as return, or the cache degenerates into "evict whatever was written longest ago" — a FIFO queue wearing an LRU label. The suite checks it directly.
A miss must store nothing. Writing -1 or a tombstone on a miss looks harmless because a later lookup still reports absent, but it consumes a slot and evicts real entries early. That is exactly what one of the tests here is built to catch, and it took a specific sequence to make visible: put('a'), two failed gets, then put('b') — a correct cache still holds both, a polluting one has already thrown a away.
Falsy values are values. if (this.map.get(key)) treats a cached 0, '' or false as a miss. Use has, or check against undefined, the same trap as memoisation.
Delete before set, always. map.set on an existing key updates the value but leaves it where it was in the insertion order, so a put that overwrites would not count as a use. Deleting first is what makes both paths reorder.
On the linked-list version. If an interviewer asks for it without Map's ordering, the shape is: a head and tail sentinel, nodes with prev/next, and a hash from key to node. Every operation unlinks a node and relinks it at the head. It is more code and the same complexity — Map is not cheating, it is the language having already built the ordered hash for you, and saying so is a better answer than reciting the list version.
Where you have met this. HTTP caches, image caches in a feed, memoisation with a bound, and React.cache-style request dedupe all need eviction. Unbounded caching is a memory leak with a friendly name.