Kata: LRU cache

The Map's order is the recency list: every hit and every put moves its key to the end, and eviction takes the first key.

Before you read: predict

ExamHall's API keeps question-bank versions in an in-process LRU cache in front of Redis. A staging test runs it as new LRUCache(2), with this kata answer:

The test calls put('ECON-201', 3), put('LAW-110', 5), then put('ECON-201', 4) (an editor republished it), then put('BIO-330', 2). Then it reads get('ECON-201'), get('LAW-110') and get('BIO-330'), in that order.

Which read returns -1?

export 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);    this.map.delete(key);    this.map.set(key, value);    return value;  }   put(key, value) {    this.map.set(key, value);    if (this.map.size > this.capacity) {      this.map.delete(this.map.keys().next().value);    }  }}

The 30-second version

A Map lists keys in insertion order, so it is the recency list: its first key is the least recently used. To mark a key used, delete it, then set it; set on a key already present keeps its place. get and put both mark. After a put, evict the first key while size exceeds capacity. Test presence, not values.

The Map's order is the recency list: every hit and every put moves its key to the end, and eviction takes the first key.

How it works

Step 1 of 11

Ask, then state the contract. Capacity, what a miss returns (LeetCode 146: -1), whether values can be falsy. Then: one Map, oldest first.

In the kitchen

the patch, with its fixed number of pins → the cache and its capacity (steps 1–2)

Analogy: A fly fisher's drying patch (angling)

A fly fisher keeps the flies she is using pinned in a row on a small patch on her vest. The patch has room for a fixed number; the rest wait in the fly box in her pocket.

On the river	In the kata
the patch, with its fixed number of pins	the cache and its capacity (steps 1–2)
the row: the fly she fished longest ago at one end, the latest at the other	the Map's key order (step 2)
she fishes a fly again: it comes off the row and is pinned at the newest end	`delete`, then `set` (steps 4–5)
a fresh copy of a pattern already on the row replaces that fly, and goes to the newest end	`put` on a stored key (steps 3, 6)
a new fly for a full patch: the fly at the oldest end goes back in the box	evicting the first key (step 7)
a fly worn down to almost nothing is still a fly on its pin, not an empty pin	a stored `0` is a hit (step 5)

In real terms: an LRU cache is a Map plus two rules: every use moves the key to the end, and the first key leaves when the cache is over capacity.

Breaks down when: she can see the whole row and pick any fly to drop. The code never looks: it takes the first key, even when that entry is the one most valuable to keep.

Contrasting case: a fisher who never re-pins and drops the fly she pinned first, however often she fishes it. That is first in, first out: a get that only reads gives exactly that.

Examples, run for real

4.1 ExamHall EXH-2860: forgetting the refresh on `get`

Each API instance keeps 500 question-bank versions in an in-process LRU in front of Redis. A draft whose get only read the Map (M1) went to production. On the day of ECON-201's exam, every request read the running exam's bank and one practice paper, each paper new (EXH-2860). MR !3160 replaced the draft with the reference and added the test list. The list also catches a second draft, M2, whose size check fires at >=.

4.1 reference-core.mjs             10 of 10 core tests pass
4.1 M1, get only reads             7 of 10 core tests pass · red: "get makes its key the most recently used", "a stored 0 is a hit and is refreshed like any value", "LeetCode 146's example 1"
4.1 M2, size >= capacity           3 of 10 core tests pass · red: "a new key over capacity evicts the least recently used key", "get makes its key the most recently used", "put on a stored key makes it the most recently used", "updating a key in a full cache evicts no other key", "a stored 0 is a hit and is refreshed like any value", "the cache holds exactly capacity keys", "LeetCode 146's example 1"
4.1 EXH-2860 M1 as the 500-version bank cache, 1,000 requests: ECON-201 loaded from Redis 2 times (missed again at request 501)
4.1 MR !3160 reference as the bank cache, same requests: ECON-201 loaded from Redis 1 time

M1 kept insertion order, so after 500 papers the exam's bank was the oldest key and went (step 5). The reference moves it to the end on every read, so it stays (step 4).

4.2 Chat: the Map's order after each call

A chat app caches each open conversation's messages in the reference, new LRUCache(3). The key order, oldest first:

4.2 put ana: ana  ->  put ben: ana · ben  ->  put cy: ana · ben · cy  ->  get ana: ben · cy · ana  ->  put dee: cy · ana · dee

Reading ana moved it to the end (step 4); dee then pushed the size past 3, and the first key, ben, went (step 7).

4.3 Cost

4.3 Map calls: one get hit 4, one put of a new key into a full cache 4; the same at 10 and at 100,000 entries

The count does not grow with the cache (step 8).

Try it

Answer first, then check. Nothing is saved.

Question 1 of 9

A chat app caches each conversation's unread count with new LRUCache(2) and this kata answer:

The app calls put('ana', 0), put('ben', 3), get('ana'), put('cy', 1), then get('ana'), get('ben') and get('cy').

What do the four get calls return, in order?

export class LRUCache {  #items = new Map();   constructor(limit) {    this.limit = limit;  }   get(id) {    const value = this.#items.get(id);    if (!value) return -1;    this.#items.delete(id);    this.#items.set(id, value);    return value;  }   put(id, value) {    this.#items.delete(id);    this.#items.set(id, value);    if (this.#items.size > this.limit) {      const [oldest] = this.#items.keys();      this.#items.delete(oldest);    }  }}

Question 2 of 9

A video app keeps the titles of its "Continue watching" row in new LRUCache(3), with this kata answer:

The app stores three titles as the viewer starts them: put('atlas', 'Atlas'), put('bonfire', 'Bonfire'), put('comet', 'Comet'). Opening the home screen draws the row newest first and reads each title: get('comet'), get('bonfire'), get('atlas'). Then the viewer starts two more: put('delta', 'Delta'), put('echo', 'Echo').

Which of the first three titles are still cached?

export class LRUCache {  constructor(capacity) {    this.capacity = capacity;    this.titles = new Map();  }   get(id) {    if (!this.titles.has(id)) return -1;    const title = this.titles.get(id);    this.titles.delete(id);    this.titles.set(id, title);    return title;  }   put(id, title) {    this.titles.delete(id);    this.titles.set(id, title);    if (this.titles.size > this.capacity) {      const [oldest] = this.titles.keys();      this.titles.delete(oldest);    }  }}

Question 3 of 9

A box office caches seat maps by event. A candidate's kata answer is complete apart from the body of get, which must return -1 for a key it does not hold:

The team's list has 10 core tests.

Which body passes all 10?

export class LRUCache {  constructor(capacity) {    this.capacity = capacity;    this.seatMaps = new Map();  }   get(eventId) {    /* the body */  }   put(eventId, seatMap) {    this.seatMaps.delete(eventId);    this.seatMaps.set(eventId, seatMap);    if (this.seatMaps.size > this.capacity) {      const [oldest] = this.seatMaps.keys();      this.seatMaps.delete(oldest);    }  }}

Question 4 of 9

A payments ledger caches account balances in new LRUCache(3), with this kata answer:

The ledger calls put('A-17', 120), put('B-02', 40), put('C-88', 75), then put('B-02', 55) after a payment. Then it reads get('A-17'), get('B-02') and get('C-88').

Which read returns -1?

export class LRUCache {  constructor(capacity) {    this.capacity = capacity;    this.balances = new Map();  }   get(account) {    if (!this.balances.has(account)) return -1;    const balance = this.balances.get(account);    this.balances.delete(account);    this.balances.set(account, balance);    return balance;  }   put(account, balance) {    if (this.balances.size === this.capacity) {      const [oldest] = this.balances.keys();      this.balances.delete(oldest);    }    this.balances.delete(account);    this.balances.set(account, balance);  }}

Question 5 of 9

the interviewer says: "Implement LRUCache with get(key) and put(key, value), both O(1) on average; get returns -1 for a missing key." You have 20 minutes and a plain editor, and ExamHall's question-bank version cache is the use case.

Before you type: say your test list out loud.

Name at least six tests, each with its calls and what it expects.

Your answer (optional, stays on this page)

Question 6 of 9

Now write it, in 20 minutes, from a blank file that exports LRUCache.

Your answer (optional, stays on this page)

Question 7 of 9

The interviewer asks: "Now give entries a time to live, and let me cap the cache by total size instead of count." Extend your class to new LRUCache(capacity, { ttl, now, maxSize, sizeOf }), where now() returns the current time and sizeOf(value) a value's size.

Answer in one or two lines.

Your answer (optional, stays on this page)

Question 8 of 9

A shop caches product records in new LRUCache(3), with this kata answer:

After put('k1', 'mug'), put('k2', 'pen'), put('k3', 'cap'), put('k4', 'bag') and put('k5', 'hat'), a get of each of the five still returns its product.

Which line, in place of the line inside the if, fixes put?

export class LRUCache {  constructor(capacity) {    this.capacity = capacity;    this.products = new Map();  }   get(sku) {    if (!this.products.has(sku)) return -1;    const product = this.products.get(sku);    this.products.delete(sku);    this.products.set(sku, product);    return product;  }   put(sku, product) {    this.products.delete(sku);    this.products.set(sku, product);    if (this.products.size > this.capacity) {      this.products.delete(this.products.entries().next().value);    }  }}

Question 9 of 9

A chat app caches attachment previews by total size, new LRUCache(12), where a preview's size is its text's length. Its kata answer has one line left to write:

Without that line, put('m1', 'aaaa'), put('m2', 'bbbb'), put('m3', 'cccccc') and then put('m2', 'dddd') leave m3 evicted, though m2 and m3 together are 10 characters.

Which line makes that sequence, followed by put('m4', 'eeee'), end with m2 and m4 cached and no other preview?

export class LRUCache {  constructor(maxBytes) {    this.maxBytes = maxBytes;    this.used = 0;    this.previews = new Map();  }   get(id) {    if (!this.previews.has(id)) return -1;    const preview = this.previews.get(id);    this.previews.delete(id);    this.previews.set(id, preview);    return preview.data;  }   put(id, data) {    const preview = { data, bytes: data.length };    /* the missing line */    this.previews.delete(id);    this.previews.set(id, preview);    this.used += preview.bytes;    while (this.used > this.maxBytes) {      const [oldest] = this.previews.keys();      this.used -= this.previews.get(oldest).bytes;      this.previews.delete(oldest);    }  }}

Go deeper

Pro tips

State the classic answer in one sentence, then say "in JS, Map insertion order gives me the list". When: the first minute, after the clarifying questions (steps 1, 9). The classic answer is a hash map plus a doubly linked list, because a hash map alone has no order. Verify: MDN says a Map's iteration "happens in insertion order"; Oracle's Java docs say HashMap's ordering is "unspecified, generally chaotic" and an access-ordered LinkedHashMap is "well-suited to building LRU caches". (The curriculum row's tip, [SELF].)

Run your own answer against the list before you call it done: KATA_IMPL=./my-lru.mjs node --test kata-core.test.mjs. When: practising the kata at home, against the tests the reference passes (step 11). Verify (RAN, tips.mjs):

tip 2 KATA_IMPL=./reference-core.mjs: exit 0 · tests 10 · pass 10 · fail 0
tip 2 KATA_IMPL=<temp>/m1-lru.mjs (get only reads): exit 1 · tests 10 · pass 7 · fail 3 · red: "get makes its key the most recently used", "a stored 0 is a hit and is refreshed like any value", "LeetCode 146's example 1"

Source

Docs and problem pages change, so their claims are labelled as of 2026-10-04; every behaviour this lesson grades is executed on Node 24.19.0.

MDN, Map (the curriculum row's first source), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map (mdn-map.txt). Iteration "happens in insertion order, which corresponds to the order in which each key-value pair was first inserted into the map by the set() method (that is, there wasn't a key with the same value already in the map when set() was called)" (steps 2–3); the specification requires maps "that, on average, provide access times that are sublinear on the number of elements in the collection" (step 8); get returns undefined "if there is none" (step 5). As of 2026-10-04.
LeetCode, 146. LRU Cache (the row's second source), https://leetcode.com/problems/lru-cache/ (leetcode-146.txt). The page itself answered 403 with a bot challenge to curl, so its statement was read from LeetCode's own API for that page (header line Via). get returns "-1" for a missing key; put evicts when "the number of keys exceeds the capacity"; both "must each run in O(1) average time complexity"; values may be 0 (steps 1, 5, 7–8). As of 2026-10-04.
MDN, Map.prototype.delete() and Map.prototype.set(), https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/delete and …/Map/set (mdn-map-delete.txt, mdn-map-set.txt): delete returns "true if an entry in the Map object has been removed successfully"; set returns "The Map object" (step 10). As of 2026-10-04.
Oracle, Java SE 21 API, Map and LinkedHashMap, https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Map.html and …/LinkedHashMap.html (java-map.txt, java-linkedhashmap.txt): put returns "the previous value associated with key"; remove "Returns the value to which this map previously associated the key"; HashMap's ordering is "unspecified, generally chaotic"; an access-ordered LinkedHashMap "is well-suited to building LRU caches". As of 2026-10-04.

Checked against the tools and docs as of 2026-10-04.

Predict first

Which read returns -1?

The 30-second version

How it works

Analogy: A fly fisher's drying patch (angling)

Examples, run for real

4.1 ExamHall EXH-2860: forgetting the refresh on get

4.2 Chat: the Map's order after each call

4.3 Cost

Try it

What do the four get calls return, in order?

Which of the first three titles are still cached?

Which body passes all 10?

Which read returns -1?

Name at least six tests, each with its calls and what it expects.

Now write it, in 20 minutes, from a blank file that exports LRUCache.

Answer in one or two lines.

Which line, in place of the line inside the if, fixes put?

Which line makes that sequence, followed by put('m4', 'eeee'), end with m2 and m4 cached and no other preview?

Go deeper

Related lessons

4.1 ExamHall EXH-2860: forgetting the refresh on `get`