Key-Value Cache With Expiry
A key/value cache where every entry expires on its own timer — and setting a key again restarts its clock.
JavaScript · ES6 — Pratik Rai ·
A fixed-size cache that evicts whatever was used least recently — and does both reads and writes in constant time.
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 -1 if 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.
Input:
JSfile.javascript1const cache = new LRUCache(3); 2 3cache.put('user:1', { name: 'Pratik' }); 4cache.put('user:2', { name: 'Rahul' }); 5cache.put('user:3', { name: 'Aman' }); 6 7cache.get('user:1'); // { name: 'Pratik' } 8 9cache.put('user:4', { name: 'Vikas' }); // over capacity 10 11cache.get('user:2'); 12cache.get('user:1');
Output:
-1
{ name: 'Pratik' }
Reading user:1 made it recently used, so when user:4 arrived the least recently used entry was user:2 — and that is the one evicted.
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.
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.
JSfile.javascript1class LRUCache { 2 constructor(capacity) { 3 this.capacity = capacity; 4 this.map = new Map(); 5 } 6 get(key) { 7 if (!this.map.has(key)) return -1; 8 const value = this.map.get(key); 9 // Delete then re-set to move it to the newest position. 10 this.map.delete(key); 11 this.map.set(key, value); 12 return value; 13 } 14 put(key, value) { 15 if (this.map.has(key)) this.map.delete(key); 16 this.map.set(key, value); 17 if (this.map.size > this.capacity) { 18 // The first key in iteration order is the oldest. 19 const oldest = this.map.keys().next().value; 20 this.map.delete(oldest); 21 } 22 } 23}
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.
Goal: Evict the least recently used entry when full, with O(1) reads and writes.
Map already gives you both, since it iterates in insertion order and map.keys().next().value reaches the oldest key without scanning.put refreshes recency, you have built a FIFO queue that evicts by age of insertion rather than by use — which will throw away the entry being read most often. It is the most common mistake in this problem.map.set on an existing key updates the value but leaves its position in the insertion order untouched, so the delete is what actually moves it to the end.Map is the language having already built an ordered hash for you, and saying that — then describing the head/tail sentinel design you would write without it — is a stronger answer than reciting the list version unprompted.Continue learning with these related challenges
A key/value cache where every entry expires on its own timer — and setting a key again restarts its clock.
JavaScript · ES6 — Pratik Rai ·
Run a list of async tasks with a hard limit on how many are in flight at once — the concurrency control Promise.all does not give you.
JavaScript · ES6 — Pratik Rai ·
Wrap an async function so it gives up after a deadline — the building block behind every request timeout.
JavaScript · ES6 — Pratik Rai ·
A key/value cache where every entry expires on its own timer — and setting a key again restarts its clock.
JavaScript · ES6
Pratik Rai ·
Run a list of async tasks with a hard limit on how many are in flight at once — the concurrency control Promise.all does not give you.
JavaScript · ES6
Pratik Rai ·
Wrap an async function so it gives up after a deadline — the building block behind every request timeout.
JavaScript · ES6
Pratik Rai ·