A cache with a size limit needs an eviction policy: when it's full and something new arrives, which entry gets thrown out? Least-Recently-Used is the workhorse answer — evict whatever hasn't been touched for the longest. It's behind HTTP caches, database buffer pools, and image caches, and it's a perennial interview question because doing it in O(1) forces you to combine a hash map with an ordering structure.
Implement lruCache(capacity) returning { get, put, size }, where every access marks a key as most-recently-used and inserts past capacity evict the least-recently-used.
function lruCache(capacity) {
return { get, put, size };
}const c = lruCache(2);
c.put('a', 1);
c.put('b', 2);
c.get('a'); // 1 — 'a' is now most-recently-used
c.put('c', 3); // capacity 2 exceeded -> evict 'b' (the LRU)
c.get('b'); // undefined
c.get('c'); // 3get hit and a put that updates an existing key both make that key most-recently-used.size past capacity, remove the least-recently-used entry (not the oldest-inserted, if it was used since).Map keeps insertion order, so its first key is the LRU and deleting-then-re-inserting a key moves it to the most-recently-used end.get returns undefined; store falsy values (0, '') faithfully.We'll lean on a Map, whose insertion order gives us the recency ranking for free: the first key is the least-recently-used, the last is the most-recently-used.
An LRU cache is a dictionary with a memory: besides mapping keys to values, it remembers when each key was last touched so it can throw out the stalest one when full. The hard part is doing both lookups and recency updates in constant time. A plain object gives O(1) lookup but no order; a plain array gives order but O(n) reordering. A Map gives you both — hashed access and a stable insertion order you can manipulate.
Picture the entries in a line from least- to most-recently-used. A Map already stores them in insertion order, so that line is literally [...map.keys()]. The front is the eviction candidate; the back is the freshest. Every operation either reads the front (to evict) or moves a key to the back (to mark it used).
Without the ordering trick, you track recency in a separate array and scan it:
function lruNaive(capacity) {
const store = new Map();
const order = []; // keys, oldest first
return {
get(key) {
if (!store.has(key)) return undefined;
order.splice(order.indexOf(key), 1); // O(n) find + shift
order.push(key);
return store.get(key);
},
put(key, value) {
store.set(key, value);
order.push(key);
if (store.size > capacity) store.delete(order.shift());
},
};
}It's correct-ish but order.indexOf and splice are O(n), and the order array drifts out of sync with store on updates (duplicate keys pile up). The insight is that the Map is the order array — no second structure, no linear scan.
function lruCache(capacity) {
const map = new Map();
function get(key) {
if (!map.has(key)) return undefined;
const value = map.get(key);
map.delete(key); // pull it out...
map.set(key, value); // ...and re-insert at the back (now MRU)
return value;
}
function put(key, value) {
if (map.has(key)) map.delete(key); // remove so re-set lands at the back
map.set(key, value);
if (map.size > capacity) {
const lruKey = map.keys().next().value; // first key = LRU
map.delete(lruKey);
}
}
return {
get,
put,
get size() {
return map.size;
},
};
}
module.exports = { lruCache };The whole design collapses into two Map moves. Touch = delete then set, which re-inserts the key at the most-recently-used end in O(1). Evict = read map.keys().next().value (the first, least-recently-used key) and delete it. No separate order list, no scanning — the Map is both the store and the queue.
lruCache(2) then put('a',1), put('b',2), get('a'), put('c',3):
put('a',1) → map [a].put('b',2) → map [a, b].get('a') → delete a, re-set → map [b, a]; returns 1. Now b is the LRU.put('c',3) → map [b, a, c], size 3 > 2 → evict map.keys().next().value which is b → map [a, c].get('b') → undefined; get('a') → 1; get('c') → 3.Because the get('a') refreshed a, the eviction correctly took b, not a.
put to an existing key must also move it to the back; otherwise a frequently-updated key can be wrongly evicted. Delete before re-setting.map.keys().next().value after the recency moves.get not counting as use — reads must refresh recency too, or the policy degrades toward least-recently-written.map.has(key), not map.get(key), so a stored 0/''/false isn't mistaken for a miss.prev/next); the Map version is that same O(1) idea with the list built in.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
A cache with a size limit needs an eviction policy: when it's full and something new arrives, which entry gets thrown out? Least-Recently-Used is the workhorse answer — evict whatever hasn't been touched for the longest. It's behind HTTP caches, database buffer pools, and image caches, and it's a perennial interview question because doing it in O(1) forces you to combine a hash map with an ordering structure.
Implement lruCache(capacity) returning { get, put, size }, where every access marks a key as most-recently-used and inserts past capacity evict the least-recently-used.
function lruCache(capacity) {
return { get, put, size };
}const c = lruCache(2);
c.put('a', 1);
c.put('b', 2);
c.get('a'); // 1 — 'a' is now most-recently-used
c.put('c', 3); // capacity 2 exceeded -> evict 'b' (the LRU)
c.get('b'); // undefined
c.get('c'); // 3get hit and a put that updates an existing key both make that key most-recently-used.size past capacity, remove the least-recently-used entry (not the oldest-inserted, if it was used since).Map keeps insertion order, so its first key is the LRU and deleting-then-re-inserting a key moves it to the most-recently-used end.get returns undefined; store falsy values (0, '') faithfully.We'll lean on a Map, whose insertion order gives us the recency ranking for free: the first key is the least-recently-used, the last is the most-recently-used.
An LRU cache is a dictionary with a memory: besides mapping keys to values, it remembers when each key was last touched so it can throw out the stalest one when full. The hard part is doing both lookups and recency updates in constant time. A plain object gives O(1) lookup but no order; a plain array gives order but O(n) reordering. A Map gives you both — hashed access and a stable insertion order you can manipulate.
Picture the entries in a line from least- to most-recently-used. A Map already stores them in insertion order, so that line is literally [...map.keys()]. The front is the eviction candidate; the back is the freshest. Every operation either reads the front (to evict) or moves a key to the back (to mark it used).
Without the ordering trick, you track recency in a separate array and scan it:
function lruNaive(capacity) {
const store = new Map();
const order = []; // keys, oldest first
return {
get(key) {
if (!store.has(key)) return undefined;
order.splice(order.indexOf(key), 1); // O(n) find + shift
order.push(key);
return store.get(key);
},
put(key, value) {
store.set(key, value);
order.push(key);
if (store.size > capacity) store.delete(order.shift());
},
};
}It's correct-ish but order.indexOf and splice are O(n), and the order array drifts out of sync with store on updates (duplicate keys pile up). The insight is that the Map is the order array — no second structure, no linear scan.
function lruCache(capacity) {
const map = new Map();
function get(key) {
if (!map.has(key)) return undefined;
const value = map.get(key);
map.delete(key); // pull it out...
map.set(key, value); // ...and re-insert at the back (now MRU)
return value;
}
function put(key, value) {
if (map.has(key)) map.delete(key); // remove so re-set lands at the back
map.set(key, value);
if (map.size > capacity) {
const lruKey = map.keys().next().value; // first key = LRU
map.delete(lruKey);
}
}
return {
get,
put,
get size() {
return map.size;
},
};
}
module.exports = { lruCache };The whole design collapses into two Map moves. Touch = delete then set, which re-inserts the key at the most-recently-used end in O(1). Evict = read map.keys().next().value (the first, least-recently-used key) and delete it. No separate order list, no scanning — the Map is both the store and the queue.
lruCache(2) then put('a',1), put('b',2), get('a'), put('c',3):
put('a',1) → map [a].put('b',2) → map [a, b].get('a') → delete a, re-set → map [b, a]; returns 1. Now b is the LRU.put('c',3) → map [b, a, c], size 3 > 2 → evict map.keys().next().value which is b → map [a, c].get('b') → undefined; get('a') → 1; get('c') → 3.Because the get('a') refreshed a, the eviction correctly took b, not a.
put to an existing key must also move it to the back; otherwise a frequently-updated key can be wrongly evicted. Delete before re-setting.map.keys().next().value after the recency moves.get not counting as use — reads must refresh recency too, or the policy degrades toward least-recently-written.map.has(key), not map.get(key), so a stored 0/''/false isn't mistaken for a miss.prev/next); the Map version is that same O(1) idea with the list built in.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.