Build challenges · 4 steps · javascript · python
LRU Cache
Build a fixed-size cache that throws away whatever was used least recently.
Every cache has to answer one awkward question: it is full, something new arrived, so what gets thrown away?
"Whatever was used least recently" is the answer that shows up in CPUs, in databases, in HTTP proxies, and in the memory manager of the machine you are reading this on. It is a good answer because it is a cheap bet on the near future: what you touched a moment ago, you will probably touch again.
You will build one across four steps, each adding a single rule:
- hold values and give them back
- throw out the oldest when you run out of room
- count reads as uses, not just writes
- count overwrites as uses too
Nothing here needs a linked list. The trick — the one every real implementation uses in some form — is that an insertion-ordered map already knows which key it saw first, and moving a key to the back is a delete followed by an insert.
The workspace
These files carry across every step. What you write in one step is what you start the next with.
- lru_cache.js
- harness.jsread-only
Steps · 0 of 4 done
Start anywhere. Open step 3 first and you are handed the reference build of steps 1 and 2, so every step stands on its own. Nothing here is locked behind anything else.
This build applies Hash Maps, Linked Lists and Caching. Read the lesson first if it is unfamiliar — a recommendation, not a prerequisite.