Implement an LRUCache class with get and put that evicts the least recently used entry.
Before you start
What's an LRU cache?
A cache keeps results you've already worked out, so asking for them again is fast: the return value of a slow function, a response you fetched, an image you decoded. Memory isn't free, so a cache has a capacity, the most entries it may hold. When it's full and a new entry arrives, an old one has to go. Throwing an entry out to make room is called evicting it.
LRU stands for least recently used. An LRU cache evicts the entry that has gone untouched the longest, where touching an entry means reading it or writing it. The bet is that what you used a moment ago you'll want again soon, and what you haven't touched in a while you probably won't.
Picture a desk with room for two books. Whenever you open a book, it goes on top of the pile. When you need a third book and the desk is full, the one at the bottom, the one you haven't opened for the longest, goes back on the shelf.
Here's a cache with room for two entries. The middle column lists what it holds after each step, most recently used first:
| Step | The cache after it | Why |
|---|---|---|
Add a | a | There's room. |
Add b | b, a | The newest entry is the most recently used. |
Read a | a, b | Reading a makes it the most recently used, so b is now the oldest. |
Add c | c, a | The cache is full, so b, the least recently used, is evicted. |
Read b | c, a | A miss: b was evicted, so there's nothing to return, and nothing moves. |
Change a's value | a, c | Writing counts as a use too. a was already there, so nothing is evicted. |
Look at the third step. Had a not been read, a would have been the oldest entry and been evicted instead of b. That's what makes it least recently used rather than first in, first out: every use moves an entry back to the front of the line.
You meet LRU caches wherever memory is limited and the same things get asked for again: memoized functions that would otherwise grow forever, caches of fetched data or decoded images, and the popular npm package lru-cache.
What do O(1) and O(n) mean?
Big O notation describes how much more work an operation does as the data grows. It ignores the exact time, which depends on the machine, and keeps only the shape of the growth. n stands for the size of the data: the number of entries, items, or characters.
| Notation | Name | As the data grows, the work | Examples |
|---|---|---|---|
O(1) | Constant | Stays the same, whether there are 10 entries or 10 million. | map.get(key), array[i], array.push(x) |
O(log n) | Logarithmic | Grows by one step each time the data doubles. | Binary search in a sorted array |
O(n) | Linear | Grows in step: twice the data, twice the work. | array.includes(x), array.shift(), one loop over everything |
O(n log n) | Linearithmic | Grows a little faster than the data. | array.sort() |
O(n²) | Quadratic | Grows with the square: twice the data, four times the work. | A loop over an array inside another loop over it |
So when a question asks for O(1) operations, it means they must not visit the entries one by one: no indexOf, no includes, no filter, and no shift() or splice() on an array, which move every element after the one removed. Looking a key up in a Map or an object is fine; it's O(1) on average.
Memory is described the same way: O(n) space means the memory used grows in step with the input.
Write a class LRUCache. new LRUCache(capacity) makes an empty cache that holds at most capacity entries.
get(key) returns the key's value, or undefined when the key isn't there. Finding it counts as using it, so it becomes the most recently used entry.
put(key, value) adds the entry, or changes the value of a key that's already there, and makes it the most recently used. If adding it puts the cache over capacity, remove the least recently used entry.
size is how many entries the cache holds.
Both get and put should be O(1).
class LRUCache {
constructor(capacity) {
// your code
}
get size() {}
get(key) {}
put(key, value) {}
}
// const cache = new LRUCache(2);
// cache.put("a", 1);
// cache.put("b", 2);
// cache.get("a"); // 1, and a is now the most recently used
// cache.put("c", 3); // over capacity: b, the least recently used, goes
// cache.get("b"); // undefined
// cache.get("c"); // 3
// cache.size; // 2
Solve it in the editor, with tests
The answer
Write it yourself first. Then compare it with a reference solution and the checks it passes.
Checking your sign-in…