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.
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, where capacity is a positive integer. Values can be anything, including 0, "", and false.
get(key) returns the value stored under key, or undefined if there's none, and counts as a use of that key.
put(key, value) adds an entry, or updates the value if the key is already there, and also counts as a use. When adding a key puts the cache over capacity, drop the least recently used entry: the one whose last use is the oldest.
size is a getter for the number of entries.
Both get and put should take O(1) time.
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // 1, so "b" is now the least recently used
cache.put("c", 3); // over capacity: drops "b"
cache.get("b"); // undefined
cache.size; // 2
const cache = new LRUCache(2);
cache.put("a", 1);
expect(cache.get("a")).toBe(1);
expect(cache.get("z")).toBeUndefined();
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
expect(cache.get("a")).toBeUndefined();
expect(cache.get("b")).toBe(2);
expect(cache.get("c")).toBe(3);
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");
cache.put("c", 3);
expect(cache.get("b")).toBeUndefined();
expect(cache.get("a")).toBe(1);
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.put("a", 10);
cache.put("c", 3);
expect(cache.get("a")).toBe(10);
expect(cache.get("b")).toBeUndefined();
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.put("b", 20);
expect(cache.size).toBe(2);
expect(cache.get("a")).toBe(1);
expect(cache.get("b")).toBe(20);
const cache = new LRUCache(3);
expect(cache.size).toBe(0);
cache.put("a", 1);
cache.put("b", 2);
expect(cache.size).toBe(2);
cache.put("c", 3);
cache.put("d", 4);
cache.put("e", 5);
expect(cache.size).toBe(3);
const cache = new LRUCache(2);
cache.put("zero", 0);
cache.put("b", 2);
expect(cache.get("zero")).toBe(0);
cache.put("c", 3);
expect(cache.get("zero")).toBe(0);
expect(cache.get("b")).toBeUndefined();
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("missing");
expect(cache.size).toBe(2);
expect(cache.get("a")).toBe(1);
expect(cache.get("b")).toBe(2);
Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.
Ctrl + Enter runs the tests (⌘ + Enter on a Mac).
I'm here to help with LRU cache. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.