Model a cache as a capacity, a Get that counts as a use, and eviction when full - then make every operation O(1). Each lesson pins an exact outcome: the least-recently-used key evicted after a scripted access order, a Get promoting a key so a later Put evicts a different one, an update promoting a key without growing the cache, capacity-1 evicting on every new key, the least-frequently-used key evicted with ties broken by recency, minFreq resetting to 1 on a fresh insert, and a TTL-expired Get missing.
Over 23 lessons you build two working caches from scratch - a least-recently-used (LRU) cache and a least-frequently-used (LFU) cache - each a small library with a fixed capacity, a Get and a Put, and O(1) eviction. Keys and values are integers so every step has an exact, assertable outcome: the precise key evicted, the exact hit and miss counts, and the exact remaining contents after a scripted sequence of operations.
You start with the cache contract on a plain map - store and retrieve, a capacity and a length, updating a key in place - as a simple insertion-order (FIFO) cache. Then you make it a real LRU: a doubly-linked list with sentinel head and tail nodes so there are no nil edge cases, a map from key to node for O(1) lookup, a hit that promotes its node to the front, and eviction that removes the tail. Next you build an LFU cache the O(1) way - a per-frequency list of keys plus a minFreq pointer, moving an entry from one frequency list to the next on each use and advancing minFreq when a list empties, with ties broken by least-recently-used. Finally you add per-entry TTL expiry, runtime resize, and hit/miss stats, and run one scripted workload through both caches to show exactly where the two eviction policies diverge.
This is a teaching-grade pair of caches built around the classic LeetCode LRU and LFU designs and the O(1) LFU scheme of Shah, Mitra, and Matani. Both caches are single-threaded and hold integer keys and values in one process, with no locking, no persistence, and a logical clock for TTL rather than wall-clock time - the honest core that production caches like Redis and Caffeine extend with concurrency, real time, admission policies, and memory accounting.
A cache is, at its heart, a lookup table you can put things into and get things back out of. Today you build that bare contract over a plain map, so the rest of the project has something concrete to make fast and to bound.
Build a cache that stores a value under a key and returns it, reporting whether the key was present.
Every cache is a lookup table with a story about what to throw away. Before any of
the throwing-away, it has to do the plain thing: store a value under a key and
give it back when asked. We will call the type LRU because that is where it
is heading, but today it is just a map with two methods.
The one detail worth pinning now is the shape of Get: it returns the value and
a boolean saying whether the key was there. A cache miss (found = false) is a
first-class outcome, not an error and not a zero value pretending to be data - the
caller needs to know the difference between “the value is 0” and “there is no
value.” Keys and values are int here so every result is a number you can assert;
making the cache generic over any key and value type is a later refinement.
// one map is the whole cache for now; capacity comes next lessontype LRU struct {cap intdata map[int]int}func NewLRU(cap int) *LRU { return &LRU{cap: cap, data: map[int]int{}} }func (c *LRU) Put(key, val int) { c.data[key] = val }func (c *LRU) Get(key int) (int, bool) { v, ok := c.data[key]; return v, ok }
A genuinely working pair of caches - O(1) Get and Put for both an LRU (doubly-linked list with sentinel nodes) and an LFU (per-frequency list plus a minFreq pointer), with per-entry TTL, runtime resize, hit/miss stats, and an eviction log, now panic-free at the capacity-0 edge - but both hold integer keys and values in a single thread with no locking, use a logical clock for TTL (LRU only), and carry one documented TTL zero-sentinel quirk.
The canonical LRU problem: a fixed-capacity cache with O(1) get and put. The classic hashmap plus doubly-linked list design this project builds, stated as a single exact-behavior exercise.
The canonical LFU problem: evict the least-frequently-used key, breaking ties by least-recently-used, all in O(1). The per-frequency list and minFreq design of the LFU chapter.
The short paper that shows LFU insert, access, and eviction can all be O(1) using frequency-keyed doubly-linked lists. The exact structure behind lessons 15 through 17.
How a production cache chooses what to evict: the allkeys-lru, allkeys-lfu, and volatile-ttl policies, and why Redis approximates LRU and LFU with sampling rather than exact lists.
A systems writeup on designing a high-performance cache: eviction policy tradeoffs, the W-TinyLFU admission filter, and why neither pure LRU nor pure LFU is enough in practice.
The classic paper that balances recency and frequency in one policy, the natural next step once you have built both an LRU and an LFU cache and seen where they diverge.