#Data Structures#Caching

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
Open Code Editor

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

  • 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.

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

Source

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

Cache With Time Limit

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

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

Promise Time Limit

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

JavaScript · ES6 — Pratik Rai ·