On this page

Capstone: Build an LRU Cache & Benchmark It

Module 1 gave you arrays, stacks, queues, linked lists and hash tables one at a time. This capstone makes you combine two of them into a structure that neither can be alone. A least-recently-used (LRU) cache has a fixed capacity, answers get(key) and put(key, value) in , and when it is full evicts the entry that was touched longest ago. The hash map gives lookup; the doubly linked list gives "move to front" and "remove from back". Interviewers ask for this structure constantly, and you will find it inside operating systems, databases, CDNs and every language's standard library.

You will build it four ways: a slow but obviously-correct reference, the real version, an LFU (least-frequently-used) variant, and then a benchmark harness that checks whether the asymptotics and the eviction policy actually show up in measurements.

Goal

When you finish you will have:

  1. An LRUCache class with get, put, hits, misses, and worst-case time per operation, in at least one language (ideally all four).
  2. A brute-force list-based cache that you trust because it is short, and a stress test that runs both against random operations and asserts they agree.
  3. An LFUCache with operations using frequency buckets.
  4. A benchmark report: hit rate under Zipfian vs uniform access, and operations per second for your cache vs the built-in alternatives.

Requirements

  • Capacity , fixed at construction. Never hold more than entries.
  • get(key): return the value if present and mark the entry as most recently used; otherwise return a sentinel (-1 for integer values, None/null otherwise). Counts as a hit or a miss.
  • put(key, value): insert or overwrite. Either way the key becomes most recently used. If the insert would exceed capacity, first evict the least recently used key. Overwriting an existing key never evicts.
  • Complexity: get and put in (expected, given the hash map); space.
  • Counters: hits and misses from get calls only (put does not count).
  • Eviction order is part of the contract: it must match the acceptance sequence below exactly.

Staged plan

flowchart LR
    P1["Part 1<br/>API + brute force<br/>+ tests"] --> P2["Part 2<br/>hash map +<br/>doubly linked list"]
    P2 --> P3["Part 3<br/>LFU with<br/>frequency buckets"]
    P3 --> P4["Part 4<br/>benchmark:<br/>hit rate + throughput"]
    P4 --> P5["Part 5<br/>write-up"]

Part 1 — the API and a brute-force version

Write the simplest cache that could be correct: a list of (key, value) pairs ordered from least to most recently used. get scans for the key, removes the pair and appends it to the end. put removes any existing pair for the key, appends the new one, and if the length exceeds pops the front. Every operation is . That is fine: this version exists to be obviously right, so it can serve as the oracle for everything else.

Write the acceptance sequence (below) as a test first and make the brute force pass it. Then write a stress test: generate 100,000 random operations over a small key space (say keys 0–9, capacity 3, so evictions happen constantly), apply each to both the brute force and the cache under test, and assert identical results after every operation. Small key spaces and small capacities find bugs fastest. This is the differential-testing technique from Testing & Debugging Algorithms.

Part 2 — hash map + doubly linked list

The brute force spends in two places: finding the entry, and moving it within the order. Fix each with one structure:

  • A hash map from key to the node holding it removes the search (Hash Tables).
  • A doubly linked list ordered by recency makes "unlink this node" and "insert at the front" , because a node knows both its neighbours (Linked Lists). A singly linked list would not do: unlinking needs the predecessor.

Use two sentinel nodes, head and tail, that are never removed. Real entries live between them, most recent next to head, least recent next to tail. Sentinels remove every special case for empty lists, single-element lists and operations at the ends: every real node always has a non-null prev and next.

flowchart LR
    H["head sentinel"] <--> A["key 4<br/>(most recent)"]
    A <--> B["key 3"]
    B <--> C["key 1<br/>(least recent)"]
    C <--> T["tail sentinel"]
    M["hash map<br/>key to node"] -.-> A
    M -.-> B
    M -.-> C

You need exactly two list primitives: unlink(node) (node.prev.next = node.next; node.next.prev = node.prev) and push_front(node) (splice between head and head.next). Then:

  • get(k): look up the node; if absent, miss. Otherwise unlink + push_front, hit, return value.
  • put(k, v): if present, update value, unlink + push_front. Otherwise, if full, take tail.prev, unlink it and delete its key from the map (this is why nodes store their key); then create a node, push_front, insert into the map.

Each is a constant number of pointer writes and hash operations. This is the same structure as the LRU sections in Linked Lists and Advanced Data Structures; here you build it, test it against an oracle, and measure it.

Part 3 — LFU with frequency buckets

LFU evicts the key with the fewest accesses, breaking ties by least recent use among them. The naive version keeps a min-heap by frequency: per operation. Shah, Mitra and Matani ("An O(1) algorithm for implementing the LFU cache eviction scheme", 2010) showed it can be with a two-level structure:

  • A map key → node (value and current frequency).
  • A map freq → doubly linked list of the nodes with that frequency, in recency order (an LRU list per frequency).
  • An integer min_freq, the smallest frequency currently present.

On access, move the node from list f to list f + 1 (both ), and if list f became empty and f == min_freq, increment min_freq. On insert of a new key, evict from the back of list min_freq if full, then insert the new node into list 1 and set min_freq = 1. min_freq only ever needs to move by one or reset to one, which is why no search is needed. In Python, OrderedDict works as the per-frequency list; in Java, LinkedHashSet.

Test LFU with the same stress-test harness and a brute-force LFU (scan for the minimum (freq, last_used_time)).

Part 4 — benchmark

Two separate measurements: hit rate (a property of the policy and the workload) and throughput (a property of the implementation).

Traces. Generate access traces over a universe of keys, 200,000 accesses each, with a fixed seed:

  • Uniform: each access picks a key uniformly at random.
  • Zipfian with exponent : key of rank is chosen with probability proportional to . Real web and cache workloads are often roughly Zipfian with between about 0.6 and 1.2. Build the cumulative distribution once and sample with binary search.

Replay each trace with "on get miss, put the key" and record the hit rate for LRU and LFU at capacities of 1% and 10% of .

Throughput. Time 1,000,000 mixed operations (e.g. 80% get, 20% put on a Zipfian trace) for your cache and the built-in alternative in your language:

  • Python: functools.lru_cache(maxsize=C) wrapped around a function, and collections.OrderedDict with move_to_end and popitem(last=False).
  • Java: LinkedHashMap constructed with accessOrder = true, overriding removeEldestEntry to return size() > capacity.
  • C++: std::list<std::pair<K, V>> plus std::unordered_map<K, std::list<...>::iterator>, using splice to move to front. Compare with your hand-written node version.
  • JavaScript/TypeScript: a plain Map — it iterates in insertion order, so "touch" is delete then set, and the LRU key is map.keys().next().value.

Warm up first (JIT languages), repeat each measurement at least 5 times and report the median, and keep the trace generation out of the timed region. The methodology in Benchmarks and your own Module 0 capstone applies directly.

Part 5 — write-up

One page: the hit-rate table, the throughput table, and three paragraphs answering: Why does the Zipfian hit rate exceed capacity/N? When did LFU beat LRU and why? Why is your hand-written cache faster or slower than the built-in? Mention memory per entry (two pointers + key + value + map overhead) using How Data Structures Live in Memory.

Acceptance tests

With capacity 2, this sequence must produce exactly these results:

#OperationReturnsCache after (MRU → LRU)Note
1put(1, 1)—1
2put(2, 2)—2, 1
3get(1)11, 2hit
4put(3, 3)—3, 1evicts 2
5get(2)−13, 1miss
6put(4, 4)—4, 3evicts 1
7get(1)−14, 3miss
8get(3)33, 4hit
9get(4)44, 3hit
10put(3, 30)—3, 4overwrite, no eviction
11put(5, 5)—5, 3evicts 4
12get(4)−15, 3miss
13get(3)303, 5hit

Final counters: hits = 4, misses = 3. Step 10 is the trap: overwriting key 3 must make it most recent, so step 11 evicts 4, not 3.

Then the stress test: 100,000 random operations, keys 0–9, capacity 3, your cache against the brute force, compared after every operation (returned value and final counters). If you have LFU, run the same harness against a brute-force LFU.

Reference solution

Try Parts 1–3 yourself first. The reference LRU below is self-checking with the acceptance sequence and, in Python, the stress test against the brute force.

Reference solution: LRU cache in four languages
import random


class _Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev: "_Node | None" = None
        self.next: "_Node | None" = None


class LRUCache:
    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be >= 1")
        self.capacity = capacity
        self.map: dict[int, _Node] = {}
        self.head, self.tail = _Node(), _Node()          # sentinels
        self.head.next, self.tail.prev = self.tail, self.head
        self.hits = self.misses = 0

    def _unlink(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node: _Node) -> None:
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            self.misses += 1
            return -1
        self.hits += 1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = _Node(key, value)
        self._push_front(node)
        self.map[key] = node


class BruteLRU:
    """O(capacity) per operation; the oracle."""

    def __init__(self, capacity: int) -> None:
        self.capacity, self.items = capacity, []         # least recent first
        self.hits = self.misses = 0

    def get(self, key: int) -> int:
        for i, (k, v) in enumerate(self.items):
            if k == key:
                self.items.append(self.items.pop(i))
                self.hits += 1
                return v
        self.misses += 1
        return -1

    def put(self, key: int, value: int) -> None:
        self.items = [(k, v) for k, v in self.items if k != key]
        self.items.append((key, value))
        if len(self.items) > self.capacity:
            self.items.pop(0)


def run_acceptance(cache) -> list[int]:
    ops = [("put", 1, 1), ("put", 2, 2), ("get", 1), ("put", 3, 3), ("get", 2), ("put", 4, 4),
           ("get", 1), ("get", 3), ("get", 4), ("put", 3, 30), ("put", 5, 5), ("get", 4), ("get", 3)]
    out = []
    for op in ops:
        if op[0] == "put":
            cache.put(op[1], op[2])
        else:
            out.append(cache.get(op[1]))
    return out


if __name__ == "__main__":
    for cls in (LRUCache, BruteLRU):
        c = cls(2)
        assert run_acceptance(c) == [1, -1, -1, 3, 4, -1, 30], cls
        assert (c.hits, c.misses) == (4, 3), cls
    rng = random.Random(7)
    fast, slow = LRUCache(3), BruteLRU(3)
    for _ in range(100_000):
        k = rng.randrange(10)
        if rng.random() < 0.6:
            assert fast.get(k) == slow.get(k)
        else:
            v = rng.randrange(1000)
            fast.put(k, v)
            slow.put(k, v)
        assert len(fast.map) <= 3
    assert (fast.hits, fast.misses) == (slow.hits, slow.misses)
    print("ALL TESTS PASSED")
import java.util.HashMap;
import java.util.Map;

public class LRUCacheDemo {

    static final class LRUCache {
        private static final class Node {
            int key, value;
            Node prev, next;
            Node(int key, int value) { this.key = key; this.value = value; }
        }

        private final int capacity;
        private final Map<Integer, Node> map = new HashMap<>();
        private final Node head = new Node(0, 0), tail = new Node(0, 0);   // sentinels
        int hits = 0, misses = 0;

        LRUCache(int capacity) {
            if (capacity < 1) throw new IllegalArgumentException("capacity must be >= 1");
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }

        private void pushFront(Node n) {
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
        }

        int get(int key) {
            Node n = map.get(key);
            if (n == null) { misses++; return -1; }
            hits++;
            unlink(n);
            pushFront(n);
            return n.value;
        }

        void put(int key, int value) {
            Node n = map.get(key);
            if (n != null) {
                n.value = value;
                unlink(n);
                pushFront(n);
                return;
            }
            if (map.size() == capacity) {
                Node lru = tail.prev;
                unlink(lru);
                map.remove(lru.key);
            }
            n = new Node(key, value);
            pushFront(n);
            map.put(key, n);
        }
    }

    public static void main(String[] args) {
        LRUCache c = new LRUCache(2);
        c.put(1, 1);
        c.put(2, 2);
        int[] got = new int[7];
        got[0] = c.get(1);
        c.put(3, 3);
        got[1] = c.get(2);
        c.put(4, 4);
        got[2] = c.get(1);
        got[3] = c.get(3);
        got[4] = c.get(4);
        c.put(3, 30);
        c.put(5, 5);
        got[5] = c.get(4);
        got[6] = c.get(3);
        int[] want = {1, -1, -1, 3, 4, -1, 30};
        if (!java.util.Arrays.equals(got, want)) throw new AssertionError(java.util.Arrays.toString(got));
        if (c.hits != 4 || c.misses != 3) throw new AssertionError("counters " + c.hits + "/" + c.misses);
        System.out.println("ALL TESTS PASSED");
    }
}
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <unordered_map>
#include <vector>

class LRUCache {
    struct Node {
        int key = 0, value = 0;
        Node* prev = nullptr;
        Node* next = nullptr;
    };
    std::size_t capacity_;
    std::unordered_map<int, Node*> map_;
    Node head_, tail_;                       // sentinels live inside the object

    void unlink(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void pushFront(Node* n) {
        n->prev = &head_;
        n->next = head_.next;
        head_.next->prev = n;
        head_.next = n;
    }

public:
    int hits = 0, misses = 0;

    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) throw std::invalid_argument("capacity must be >= 1");
        head_.next = &tail_;
        tail_.prev = &head_;
    }
    ~LRUCache() { for (auto& [k, n] : map_) delete n; }
    LRUCache(const LRUCache&) = delete;
    LRUCache& operator=(const LRUCache&) = delete;

    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) { ++misses; return -1; }
        ++hits;
        unlink(it->second);
        pushFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            it->second->value = value;
            unlink(it->second);
            pushFront(it->second);
            return;
        }
        if (map_.size() == capacity_) {
            Node* lru = tail_.prev;
            unlink(lru);
            map_.erase(lru->key);
            delete lru;
        }
        Node* n = new Node{key, value};
        pushFront(n);
        map_[key] = n;
    }
};

int main() {
    LRUCache c(2);
    std::vector<int> got;
    c.put(1, 1);
    c.put(2, 2);
    got.push_back(c.get(1));
    c.put(3, 3);
    got.push_back(c.get(2));
    c.put(4, 4);
    got.push_back(c.get(1));
    got.push_back(c.get(3));
    got.push_back(c.get(4));
    c.put(3, 30);
    c.put(5, 5);
    got.push_back(c.get(4));
    got.push_back(c.get(3));
    assert((got == std::vector<int>{1, -1, -1, 3, 4, -1, 30}));
    assert(c.hits == 4 && c.misses == 3);
    std::cout << "ALL TESTS PASSED\n";
    return 0;
}
interface LNode {
  key: number;
  value: number;
  prev: LNode | null;
  next: LNode | null;
}

class LRUCache {
  private map = new Map<number, LNode>();
  private head: LNode = { key: 0, value: 0, prev: null, next: null };   // sentinels
  private tail: LNode = { key: 0, value: 0, prev: null, next: null };
  private capacity: number;
  hits = 0;
  misses = 0;

  constructor(capacity: number) {
    if (capacity < 1) throw new Error("capacity must be >= 1");
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private unlink(n: LNode): void {
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
  }

  private pushFront(n: LNode): void {
    n.prev = this.head;
    n.next = this.head.next;
    this.head.next!.prev = n;
    this.head.next = n;
  }

  get(key: number): number {
    const n = this.map.get(key);
    if (n === undefined) { this.misses++; return -1; }
    this.hits++;
    this.unlink(n);
    this.pushFront(n);
    return n.value;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.unlink(existing);
      this.pushFront(existing);
      return;
    }
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev!;
      this.unlink(lru);
      this.map.delete(lru.key);
    }
    const n: LNode = { key, value, prev: null, next: null };
    this.pushFront(n);
    this.map.set(key, n);
  }
}

const c = new LRUCache(2);
const got: number[] = [];
c.put(1, 1);
c.put(2, 2);
got.push(c.get(1));
c.put(3, 3);
got.push(c.get(2));
c.put(4, 4);
got.push(c.get(1));
got.push(c.get(3));
got.push(c.get(4));
c.put(3, 30);
c.put(5, 5);
got.push(c.get(4));
got.push(c.get(3));
if (JSON.stringify(got) !== JSON.stringify([1, -1, -1, 3, 4, -1, 30])) throw new Error(`got ${got}`);
if (c.hits !== 4 || c.misses !== 3) throw new Error(`counters ${c.hits}/${c.misses}`);
console.log("ALL TESTS PASSED");
Reference solution: O(1) LFU (Python)
from collections import OrderedDict, defaultdict


class LFUCache:
    """Shah-Mitra-Matani style: key -> (value, freq), freq -> recency-ordered keys, min_freq."""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.vals: dict[int, int] = {}
        self.freq: dict[int, int] = {}
        self.buckets: defaultdict[int, OrderedDict] = defaultdict(OrderedDict)
        self.min_freq = 0

    def _touch(self, key: int) -> None:
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None          # most recent within its bucket

    def get(self, key: int) -> int:
        if key not in self.vals:
            return -1
        self._touch(key)
        return self.vals[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.capacity:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)   # LRU among least frequent
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.vals[victim], self.freq[victim]
        self.vals[key], self.freq[key] = value, 1
        self.buckets[1][key] = None
        self.min_freq = 1


lfu = LFUCache(2)
lfu.put(1, 1); lfu.put(2, 2)
assert lfu.get(1) == 1          # freq(1) = 2
lfu.put(3, 3)                   # evicts 2 (freq 1)
assert lfu.get(2) == -1
assert lfu.get(3) == 3          # freq(3) = 2, tie with 1; 1 is less recent
lfu.put(4, 4)                   # evicts 1
assert lfu.get(1) == -1 and lfu.get(3) == 3 and lfu.get(4) == 4
print("ok")

Every operation is a constant number of dictionary and OrderedDict operations: expected. This matches LeetCode 460 (LFU Cache).

What the numbers should look like

These figures come from a simulation of LRU with keys and 200,000 accesses (seed 42); your exact values will differ with your generator and seed, but the shape should match.

WorkloadCapacity 1,000 (10%)Capacity 100 (1%)
Uniform≈ 0.10≈ 0.01
Zipf ≈ 0.43—
Zipf ≈ 0.67≈ 0.39
Zipf ≈ 0.86—

What to notice:

  • Uniform access defeats every policy. The hit rate is capacity / N, because no key is more likely than another; LRU, LFU and random eviction all converge to the same number. If your uniform hit rate is far from , your benchmark has a bug.
  • Skew is what caches exploit. Under Zipf , 10% of the keys capture about 67% of accesses with LRU. The probability mass of the 1,000 most popular keys is about 0.77, which is the hit rate of an ideal "keep the most popular" cache; LRU lands below that because it sometimes evicts a popular key after a run of one-off accesses.
  • LFU tends to beat LRU on stationary Zipf traces (popularity does not change, so frequency is the right signal) and to lose when popularity shifts over time (old popular keys squat in the cache). Expect the gap to be a few percentage points; treat this as a hypothesis your benchmark should test, not a guaranteed result.
  • Throughput. A hand-written LRU in C++ or Java should do tens of millions of operations per second for small keys; the cost is dominated by the hash lookup and by cache misses on node pointers. In Python, OrderedDict and functools.lru_cache are implemented in C and will usually beat a pure-Python node-based LRU by several times. That is a lesson worth writing down: the asymptotics are the same, and the constant factor comes from the language runtime, not from the algorithm (Complexity Analysis).

Stretch goals

  1. TTL expiry. Add a time-to-live per entry; get treats expired entries as misses and removes them. Lazy expiry (check on access) is ; to reclaim memory eagerly, keep a min-heap or timing wheel of expiry times.
  2. Thread safety. Wrap operations in a lock and measure throughput with 1, 2, 4 and 8 threads. Then shard: independent caches selected by hash(key) % S, each with its own lock. Compare with Java's ConcurrentHashMap-based caches such as Caffeine.
  3. Better policies. Read about and implement one of: segmented LRU / 2Q (a probationary queue so one-off keys cannot evict proven ones), ARC (Megiddo and Modha, 2003: adaptively balances recency and frequency), or W-TinyLFU (Einziger, Friedman and Manes, 2017: a Count-Min-style frequency sketch gates admission; this is Caffeine's policy). The frequency sketch connects directly to Bloom Filters, Count-Min Sketch & Probabilistic Structures. Run each on your Zipf and shifting traces.
  4. Approximate LRU. Redis does not keep a linked list: it samples a handful of keys (maxmemory-samples, default 5) and evicts the one with the oldest access timestamp. Implement sampled eviction and measure how close it gets to exact LRU's hit rate as the sample size grows. See Redis Internals and Caching Strategies.
  5. Array-backed list. Replace node objects with parallel arrays of prev/next indices (the trick from Queues, Deques & Circular Buffers). Measure the throughput change; explain it in terms of allocation and cache locality.

Further reading

Module 1 navigation. Previous: Bloom Filters, Count-Min Sketch & Probabilistic Structures. Module overview: Linear Data Structures. Course home: DSA: Zero to Mastery.