#Data Structures#Caching

Build an LRU Cache

A fixed-size cache that evicts whatever was used least recently — and does both reads and writes in constant time.

By Pratik RaiMedium

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.

Examples

Input:

JSfile.javascript
1const 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.

Constraints

  • capacity is a positive whole number
  • 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.

How to solve it

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

JSfile.javascript
1class 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}

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.

Goal: Evict the least recently used entry when full, with O(1) reads and writes.

Frequently asked questions

What is an LRU cache?
A cache with a fixed capacity that, when it runs out of room, discards whichever entry was used least recently. It is the standard policy when you want bounded memory and expect recent items to be the ones asked for again.
How do you get O(1) for both get and put?
Pair a hash map for lookup with something that maintains order in constant time — classically a doubly linked list, where each map entry points at its node. In JavaScript a Map already gives you both, since it iterates in insertion order and map.keys().next().value reaches the oldest key without scanning.
Why does get need to reorder anything?
Because reading an entry counts as using it. If only 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.
How do you move a key to the most recently used position in a Map?
Delete it and set it again. 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.
What happens if you store something on a cache miss?
It quietly consumes a slot. A later lookup still reports the key as absent, so the bug is invisible directly — but the junk occupies capacity and evicts real entries earlier than it should. A miss should change nothing about the cache.
Is using a Map instead of a linked list a cop-out in an interview?
No, provided you can explain the linked-list version. 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.
How is an LRU cache different from a TTL cache?
An LRU cache evicts by use once it hits a size limit; a TTL cache evicts by age regardless of size. They solve different problems and are often combined: bounded memory plus a freshness guarantee.

Related Challenges

Continue learning with these related challenges

View All
JavaScript

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 ·

JavaScript

Promise Pool With a Concurrency Limit

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 ·

JavaScript

Time Out an Async Function

Wrap an async function so it gives up after a deadline — the building block behind every request timeout.

JavaScript · ES6 — Pratik Rai ·