Implement an LRU cache with O(1) get and put using a hash map and a doubly linked list.
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's a doubly linked list?
An array keeps its items in numbered slots, so you can jump straight to any index. A linked list keeps each item in its own small object, a node, and each node holds a reference to the next one. There are no indexes: to reach the fifth item, you start at the first node and follow next four times.
In a doubly linked list, each node also points back to the node before it, through prev:
const a = { value: "a", prev: null, next: null };
const b = { value: "b", prev: null, next: null };
const c = { value: "c", prev: null, next: null };
a.next = b; b.prev = a;
b.next = c; c.prev = b;
// a <-> b <-> c
Its strength is that once you're holding a node, you can take it out, or put a node next to it, by changing a few references, however long the list is. Nothing shifts along as it does in an array. Taking b out only touches its two neighbours:
b.prev.next = b.next; // a now points forward to c
b.next.prev = b.prev; // c now points back to a
// a <-> c
In a singly linked list, with only next, you'd first have to walk from the start to find the node before b. The prev reference saves that walk.
The catch is finding a node in the first place: by value or by position, that's still a walk from one end. A linked list is fast only for changes around a node you already hold.
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, and keys() returns their keys as an array, from the most to the least recently used.
Both get and put must be O(1). A Map already remembers the order its keys were added in, but here you may only use it to look up an entry by key. Keep the order yourself, in a doubly linked list you write, as you would in a language whose maps don't keep order.
class LRUCache {
constructor(capacity) {
// your code
}
get size() {}
get(key) {}
put(key, value) {}
keys() {}
}
// const cache = new LRUCache(2);
// cache.put("a", 1);
// cache.put("b", 2);
// cache.keys(); // ["b", "a"]: b was used last
// cache.get("a"); // 1, and a is now the most recently used
// cache.keys(); // ["a", "b"]
// cache.put("c", 3); // over capacity: b, the least recently used, goes
// cache.keys(); // ["c", "a"]
// cache.get("b"); // undefined
// cache.size; // 2
The answer
Write it yourself first. Then compare it with a reference solution and the checks it passes.
Checking your sign-in…