Module 18: LRU/LFU Cache & Rate Limiter

Why this matters

Three classic problems, back to the multi-problem format of modules 12–14 — but with a different question driving the design than any module so far. For LRU and LFU, the requirement isn't a behavior to model, it's a complexity bound: every operation must run in O(1). No single data structure gets you there alone — a hash map alone can't track recency or frequency order in O(1); a linked list alone can't look up a key in O(1). The design is the combination. This is the module where "what pattern applies here?" is the wrong first question, and "what data structures, combined, give me the required complexity?" is the right one. The Rate Limiter closes the module with a smaller but genuine point: its clock is passed in as a dependency rather than called directly, which is exactly what makes it possible to test deterministically — a preview of module 19's dependency-injection theme, arrived at here for a very concrete reason (you cannot unit-test time-based behavior against the real clock).

Problem 1: LRU Cache

Requirements

Functional: a fixed-capacity cache supports get(key) (returns the value, or "miss") and put(key, value). Every access to a key marks it as most-recently-used; when a put would exceed capacity, the least-recently-used key is evicted.

Non-functional: both get and put must run in O(1) time.

Assumptions stated up front (module 11, step 1): keys and values are simple comparable types (ints, in the examples below); capacity is fixed at construction, not resizable.

Entities and relationships

Applying module 11's steps 3–4: LRUCache o-- Node (composition, many — each cached entry is one node in an internal doubly linked list); LRUCache --> Node via a hash map for O(1) lookup (association, not ownership duplication — the map and the list both reference the same node objects, they don't hold separate copies).

Class diagram

┌──────────────┐      ┌──────────────┐
│   LRUCache   │ o──  │     Node     │
├──────────────┤      ├──────────────┤
│ - capacity   │      │ - key, value │
│ - cache      │      │ - prev, next │
│ - head, tail │      └──────────────┘
├──────────────┤
│ + get()      │
│ + put()      │
└──────────────┘

Implementation

The combination that makes O(1) possible: a hash map from key to Node gives O(1) lookup; a doubly linked list of those same Nodes, ordered by recency, gives O(1) reordering (unlink + relink, no shifting) and O(1) eviction (remove from the tail end). Neither structure alone provides both lookup and order in O(1) — together they do.

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict[int, Node] = {}
        self.head = Node()             # sentinel — most-recently-used side
        self.tail = Node()             # sentinel — least-recently-used side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_front(self, node: Node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> "int | None":
        if key not in self.cache:
            return None
        node = self.cache[key]
        self._remove(node)
        self._insert_at_front(node)     # touched — now most recently used
        return node.value

    def put(self, key: int, value: int):
        if key in self.cache:
            self._remove(self.cache[key])
        elif len(self.cache) >= self.capacity:
            lru = self.tail.prev                    # least-recently-used node
            self._remove(lru)
            del self.cache[lru.key]

        node = Node(key, value)
        self._insert_at_front(node)
        self.cache[key] = node

# usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1 -> touches 1: order becomes 1(MRU), 2(LRU)
cache.put(3, 3)         # evicts 2 (LRU)
print(cache.get(2))    # None
cache.put(4, 4)         # evicts 1 (LRU)
print(cache.get(1))    # None
print(cache.get(3))    # 3
print(cache.get(4))    # 4

public class Node {
    public int Key, Value;
    public Node Prev, Next;
    public Node(int key = 0, int value = 0) { Key = key; Value = value; }
}

public class LRUCache {
    private int _capacity;
    private Dictionary<int, Node> _cache = new Dictionary<int, Node>();
    private Node _head = new Node();     // sentinel — most-recently-used side
    private Node _tail = new Node();     // sentinel — least-recently-used side

    public LRUCache(int capacity) {
        _capacity = capacity;
        _head.Next = _tail;
        _tail.Prev = _head;
    }

    private void Remove(Node node) {
        node.Prev.Next = node.Next;
        node.Next.Prev = node.Prev;
    }

    private void InsertAtFront(Node node) {
        node.Next = _head.Next;
        node.Prev = _head;
        _head.Next.Prev = node;
        _head.Next = node;
    }

    public int? Get(int key) {
        if (!_cache.TryGetValue(key, out var node)) return null;
        Remove(node);
        InsertAtFront(node);              // touched — now most recently used
        return node.Value;
    }

    public void Put(int key, int value) {
        if (_cache.TryGetValue(key, out var existing)) {
            Remove(existing);
        } else if (_cache.Count >= _capacity) {
            var lru = _tail.Prev;                     // least-recently-used node
            Remove(lru);
            _cache.Remove(lru.Key);
        }

        var node = new Node(key, value);
        InsertAtFront(node);
        _cache[key] = node;
    }
}

// usage
var cache = new LRUCache(2);
cache.Put(1, 1);
cache.Put(2, 2);
Console.WriteLine(cache.Get(1));      // 1 -> touches 1: order becomes 1(MRU), 2(LRU)
cache.Put(3, 3);                       // evicts 2
Console.WriteLine(cache.Get(2));      // null
cache.Put(4, 4);                       // evicts 1
Console.WriteLine(cache.Get(1));      // null
Console.WriteLine(cache.Get(3));      // 3
Console.WriteLine(cache.Get(4));      // 4

Tradeoffs and extensions

• Sentinel head/tail nodes remove every "is this the first/last node?" edge case from _remove/Remove and _insert_at_front/InsertAtFront — every real node always has a genuine prev and next to relink, even at the boundaries. This is a small technique worth naming: it trades two always-allocated dummy nodes for the removal of an entire class of off-by-one bugs.
• The hash map stores Node references, not copies — cache and the linked list both point at the same objects, so moving a node in the list is instantly visible through the map with no synchronization needed between two data structures pretending to be independent.

Problem 2: LFU Cache

Requirements

Functional: like LRU, but eviction is driven by access frequency instead of recency — the least-frequently-used key is evicted on overflow. Ties (multiple keys at the same minimum frequency) are broken by recency: the least-recently-used key among the tied minimum-frequency keys is evicted.

Non-functional: both get and put must run in O(1) time — same bound as LRU, harder to hit because frequency introduces a second ordering dimension.

Assumptions: same as LRU — simple key/value types, fixed capacity; a capacity of 0 means every put is a no-op (named edge case, tested below).

Class diagram

┌─────────────────────┐
│       LFUCache      │
├─────────────────────┤
│ - capacity, minFreq │
│ - keyToValue        │
│ - keyToFreq         │
│ - freqToKeys        │
├─────────────────────┤
│ + get()             │
│ + put()             │
└─────────────────────┘

Implementation

The idea that makes O(1) possible here: instead of one ordered structure, keep one ordered structure per frequency. freqToKeys maps each frequency to an ordered collection of the keys currently at that frequency (oldest-touched first) — an LRU list within each frequency bucket. Tracking minFreq separately means eviction never has to search for the minimum; it's always known.

from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_value: dict[int, int] = {}
        self.key_to_freq: dict[int, int] = {}
        self.freq_to_keys: dict[int, OrderedDict] = defaultdict(OrderedDict)   # freq -> keys, insertion order = recency

    def _bump_freq(self, key: int):
        freq = self.key_to_freq[key]
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq] and self.min_freq == freq:
            self.min_freq += 1
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = None

    def get(self, key: int) -> "int | None":
        if key not in self.key_to_value:
            return None
        self._bump_freq(key)
        return self.key_to_value[key]

    def put(self, key: int, value: int):
        if self.capacity == 0:
            return
        if key in self.key_to_value:
            self.key_to_value[key] = value
            self._bump_freq(key)
            return

        if len(self.key_to_value) >= self.capacity:
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)   # least-recently-used at min frequency
            del self.key_to_value[evict_key]
            del self.key_to_freq[evict_key]

        self.key_to_value[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

# usage
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1 -> freq(1)=2, freq(2)=1
cache.put(3, 3)         # evicts key 2 (min freq, only key there)
print(cache.get(2))    # None
print(cache.get(3))    # 3 -> freq(3)=2
cache.put(4, 4)         # freq(1)=2, freq(3)=2 tie -> evicts 1 (touched before 3)
print(cache.get(1))    # None
print(cache.get(3))    # 3
print(cache.get(4))    # 4

public class LFUCache {
    private int _capacity;
    private int _minFreq;
    private Dictionary<int, int> _keyToValue = new Dictionary<int, int>();
    private Dictionary<int, int> _keyToFreq = new Dictionary<int, int>();
    private Dictionary<int, LinkedList<int>> _freqToKeys = new Dictionary<int, LinkedList<int>>();
    private Dictionary<int, LinkedListNode<int>> _keyToNode = new Dictionary<int, LinkedListNode<int>>();

    public LFUCache(int capacity) { _capacity = capacity; }

    private LinkedList<int> GetFreqList(int freq) {
        if (!_freqToKeys.TryGetValue(freq, out var list)) {
            list = new LinkedList<int>();
            _freqToKeys[freq] = list;
        }
        return list;
    }

    private void BumpFreq(int key) {
        int freq = _keyToFreq[key];
        var oldList = _freqToKeys[freq];
        oldList.Remove(_keyToNode[key]);
        if (oldList.Count == 0 && _minFreq == freq) _minFreq++;

        _keyToFreq[key] = freq + 1;
        var newList = GetFreqList(freq + 1);
        _keyToNode[key] = newList.AddLast(key);
    }

    public int? Get(int key) {
        if (!_keyToValue.ContainsKey(key)) return null;
        BumpFreq(key);
        return _keyToValue[key];
    }

    public void Put(int key, int value) {
        if (_capacity == 0) return;
        if (_keyToValue.ContainsKey(key)) {
            _keyToValue[key] = value;
            BumpFreq(key);
            return;
        }

        if (_keyToValue.Count >= _capacity) {
            var minList = _freqToKeys[_minFreq];
            int evictKey = minList.First.Value;          // least-recently-used at min frequency
            minList.RemoveFirst();
            _keyToValue.Remove(evictKey);
            _keyToFreq.Remove(evictKey);
            _keyToNode.Remove(evictKey);
        }

        _keyToValue[key] = value;
        _keyToFreq[key] = 1;
        _keyToNode[key] = GetFreqList(1).AddLast(key);
        _minFreq = 1;
    }
}

// usage
var cache = new LFUCache(2);
cache.Put(1, 1);
cache.Put(2, 2);
Console.WriteLine(cache.Get(1));      // 1 -> freq(1)=2, freq(2)=1
cache.Put(3, 3);                       // evicts key 2 (min freq, only key there)
Console.WriteLine(cache.Get(2));      // null
Console.WriteLine(cache.Get(3));      // 3 -> freq(3)=2
cache.Put(4, 4);                       // freq(1)=2, freq(3)=2 tie -> evicts 1 (touched before 3)
Console.WriteLine(cache.Get(1));      // null
Console.WriteLine(cache.Get(3));      // 3
Console.WriteLine(cache.Get(4));      // 4

Tradeoffs and extensions

• minFreq is tracked incrementally, never recomputed by scanning. It only ever increases by 1 at a time (when a key's old frequency bucket empties out) or resets to 1 (on a fresh insert) — an O(n) "find the minimum" scan would silently break the O(1) requirement this whole design exists to satisfy.
• Frequency ties are broken by recency, using the exact same ordered-collection technique as the LRU cache above — this is effectively "an LRU cache per frequency bucket." Problem 2 doesn't introduce a new eviction-ordering idea, it reuses Problem 1's inside each bucket.
• Python's OrderedDict and C#'s LinkedList<T> + node-reference-map play the same role as LRUCache's hand-rolled doubly linked list — OrderedDict already is a hash-map-plus- order structure, so Python gets it from the standard library, while C# needs the explicit LinkedList<int> + Dictionary<int, LinkedListNode<int>> pairing to get the same O(1) guarantees.

Problem 3: Rate Limiter

Requirements

Functional: given a maximum request rate, decide for each incoming request whether to allow or reject it. Requests may burst up to a capacity, then must wait for capacity to refill over time (token bucket algorithm).

Non-functional: must be correct under concurrent callers (module 10); must be testable without depending on real wall-clock time or sleep-based tests, which are slow and flaky.

Assumptions stated up front (module 11, step 1): a single shared bucket per limiter instance (per-user or per-endpoint limiting is a named extension); token refill is continuous (fractional tokens accumulate between requests), not a fixed per-second reset.

Class diagram

┌────────────────────────┐
│ TokenBucketRateLimiter │
├────────────────────────┤
│ - capacity             │
│ - refillRate           │
│ - tokens               │
│ - lastRefill           │
│ - clock                │
├────────────────────────┤
│ + allowRequest()       │
└────────────────────────┘

Implementation

The clock is a constructor parameter, not a direct call to time.monotonic()/DateTime.Now inside the class — this is dependency injection (a preview of module 19) for a concrete reason: the tests below drive a fake clock manually instead of sleeping in real time, making the refill behavior deterministic and fast to test.

import threading
import time

class TokenBucketRateLimiter:
    def __init__(self, capacity: int, refill_rate_per_sec: float, clock=time.monotonic):
        self.capacity = capacity
        self.refill_rate = refill_rate_per_sec
        self._clock = clock                       # injected time source — swap for a fake clock in tests
        self._tokens = float(capacity)
        self._last_refill = self._clock()
        self._lock = threading.Lock()

    def _refill(self):
        now = self._clock()
        elapsed = now - self._last_refill
        self._tokens = min(self.capacity, self._tokens + elapsed * self.refill_rate)
        self._last_refill = now

    def allow_request(self) -> bool:
        with self._lock:                           # critical section: check-then-consume over shared token count
            self._refill()
            if self._tokens >= 1:
                self._tokens -= 1
                return True
            return False

# usage — with a fake, manually-advanced clock: deterministic, no real sleeping
class FakeClock:
    def __init__(self):
        self.now = 0.0
    def advance(self, seconds):
        self.now += seconds
    def __call__(self):
        return self.now

clock = FakeClock()
limiter = TokenBucketRateLimiter(capacity=3, refill_rate_per_sec=1.0, clock=clock)

print(limiter.allow_request())   # True
print(limiter.allow_request())   # True
print(limiter.allow_request())   # True
print(limiter.allow_request())   # False -> bucket empty, no time has passed

clock.advance(1.0)                # 1 second passes -> 1 token refills
print(limiter.allow_request())   # True
print(limiter.allow_request())   # False

public class TokenBucketRateLimiter {
    private int _capacity;
    private double _refillRatePerSec;
    private Func<double> _clock;               // injected time source — swap for a fake clock in tests
    private double _tokens;
    private double _lastRefill;
    private readonly object _lock = new object();

    public TokenBucketRateLimiter(int capacity, double refillRatePerSec, Func<double> clock) {
        _capacity = capacity;
        _refillRatePerSec = refillRatePerSec;
        _clock = clock;
        _tokens = capacity;
        _lastRefill = clock();
    }

    private void Refill() {
        double now = _clock();
        double elapsed = now - _lastRefill;
        _tokens = Math.Min(_capacity, _tokens + elapsed * _refillRatePerSec);
        _lastRefill = now;
    }

    public bool AllowRequest() {
        lock (_lock) {                          // critical section: check-then-consume over the shared token count
            Refill();
            if (_tokens >= 1) {
                _tokens -= 1;
                return true;
            }
            return false;
        }
    }
}

// usage — with a fake, manually-advanced clock: deterministic, no real sleeping
public class FakeClock {
    public double Now = 0.0;
    public void Advance(double seconds) => Now += seconds;
    public double Get() => Now;
}

var clock = new FakeClock();
var limiter = new TokenBucketRateLimiter(capacity: 3, refillRatePerSec: 1.0, clock: clock.Get);

Console.WriteLine(limiter.AllowRequest());  // true
Console.WriteLine(limiter.AllowRequest());  // true
Console.WriteLine(limiter.AllowRequest());  // true
Console.WriteLine(limiter.AllowRequest());  // false — bucket empty

clock.Advance(1.0);                          // 1 second passes -> 1 token refills
Console.WriteLine(limiter.AllowRequest());  // true
Console.WriteLine(limiter.AllowRequest());  // false

Tradeoffs and extensions

• The clock is injected, not hardcoded — the single design choice that makes this class testable at all without real sleep calls in the test suite. This is dependency injection earning its keep for a concrete reason, ahead of module 19's fuller treatment of the idea.
• The lock protects the same check-then-consume shape every concurrency-critical module in this track has used (Level. find_and_assign, Show.book_seats, RideManager's driver match): refill-then-check-then-decrement happens inside one locked method, never split across calls a race could interleave.
• Token bucket vs. fixed window: a simpler "reset counter every N seconds" rate limiter is easier to implement but allows a burst of 2×limit requests right at a window boundary (a flood just before the reset, followed immediately by another flood just after). Token bucket's continuous refill avoids that edge case — named here as the reason to prefer it, not just an arbitrary implementation choice.
• One bucket per limiter instance is a named simplification — a real API gateway keys a separate bucket per user or per endpoint (extension: wrap this class in a dict[key, TokenBucketRateLimiter] keyed by whatever dimension needs independent limits).

Hands-on exercises

1. LRU: verify O(1) is really being achieved

Add a counter to _remove/Remove and _insert_at_front/InsertAtFront that counts how many nodes each call touches. Confirm it's always a small constant, regardless of cache size — never proportional to the number of cached entries.

2. LFU: handle the zero-capacity edge case explicitly

Confirm (or add a test proving) that LFUCache(0) makes every put a no-op and every get a miss, without raising an error.

3. LFU: implement get_frequency(key)

Add a debug method returning a key's current access frequency, useful for writing your own tie-breaking tests.

4. Rate limiter: implement a fixed-window variant

Implement FixedWindowRateLimiter (reset a counter every N seconds instead of continuous refill), and write a test using the same fake-clock technique that demonstrates the boundary-burst problem named in the tradeoffs above — a flood of requests right before a window reset, followed by another flood right after.

5. Rate limiter: per-key limiting

Wrap TokenBucketRateLimiter in a class that maintains one bucket per key (e.g., per user ID), creating buckets lazily on first use, all sharing the same capacity and refill rate.

Independent challenge

No code given.

Task: Implement an LRU cache with per-entry TTL (time-to-live). Each put(key, value, ttl_seconds) should make the entry inaccessible via get once ttl_seconds have elapsed, in addition to normal LRU eviction on capacity overflow — whichever happens first. Use the same injected-clock technique as the rate limiter for testability (don't call the real clock directly inside the cache). Confirm a key that's still within capacity but past its TTL returns a miss, and a key that's evicted for capacity reasons is unaffected by whether its TTL had expired.

Common mistakes & troubleshooting

• Using a plain (singly linked or array-backed) list for LRU ordering. Removing an arbitrary node from an array means shifting every element after it — O(n), not O(1). The doubly linked list is what makes removal from the middle O(1); losing that is the most common way this problem's complexity requirement quietly breaks.
• Forgetting sentinel nodes and hand-rolling null checks for "is this the head/tail?" at every _remove/_insert_at_front call site. This is exactly the class of edge-case bug sentinels are designed to eliminate — every real node always has a genuine neighbor to relink.
• LFU: recomputing min_freq by scanning all frequencies instead of tracking it incrementally. This silently turns an O(1) operation into O(n) (or O(number of distinct frequencies)) and defeats the entire point of the design.
• LFU: forgetting the frequency-tie-breaks-by-recency rule, and evicting an arbitrary key at the minimum frequency instead of the least-recently-used one among them. This is the detail that makes LFU meaningfully different from "just group by frequency."
• Rate limiter: calling the real clock directly inside the class instead of accepting it as a parameter. This makes correct, deterministic tests of time-based behavior effectively impossible without slow, flaky sleep-based tests.

Checkpoint quiz

1. Why does LRU need both a hash map and a doubly linked list — what does each one provide that the other can't?
2. Why are head/tail sentinel nodes used instead of letting head/tail be None when the list is empty?
3. Why is min_freq tracked incrementally in LFU instead of recomputed on demand?
4. What extra rule does LFU apply that a plain "group keys by frequency" design would miss?
5. Why is the rate limiter's clock passed in as a parameter instead of called directly inside the class?

Interview questions

1. "How would you implement an LRU cache with O(1) get and put?" A hash map from key to node for O(1) lookup, combined with a doubly linked list (with sentinel head/tail nodes) ordered by recency for O(1) reordering and O(1) eviction from the least-recently-used end. Neither structure alone achieves both requirements; the combination does.
2. "How is an LFU cache different from an LRU cache, and how do you still get O(1)?" LFU evicts by access frequency instead of recency, with ties broken by recency. O(1) comes from keeping one ordered (LRU-style) structure per frequency bucket, plus an incrementally-tracked minFreq so the eviction target is always known without scanning.
3. "Walk me through the token bucket algorithm." A bucket holds up to capacity tokens, refilling continuously at refillRate tokens per second based on elapsed time since the last check. Each allowed request consumes one token; a request is rejected if fewer than one token is available. This permits bursts up to the bucket's capacity while enforcing a long-run average rate.
4. "Why prefer token bucket over a simple fixed-window counter for rate limiting?" A fixed window (reset a counter every N seconds) allows up to 2×limit requests clustered right around a window boundary — a flood just before reset, immediately followed by another flood just after. Token bucket's continuous refill has no such boundary to exploit.
5. "How would you test time-dependent logic like a rate limiter without making the test suite slow or flaky?" Inject the time source as a constructor parameter instead of calling the real clock directly inside the class, then drive a fake, manually-advanced clock in tests — deterministic and instant, with no real sleep calls involved.

Further reading & sources

• LeetCode 146: LRU Cache - the canonical version of Problem 1, useful for timed practice after working through this module.
• LeetCode 460: LFU Cache - the canonical version of Problem 2, including the exact tie-breaking rule implemented here.
• Token bucket (Wikipedia) - the general algorithm Problem 3 implements, including the burst-vs-average-rate tradeoff discussed above.

Next

19-api-library-design-and-di — designing a clean, versioned, fluent public API/SDK, and applying dependency injection for testability (the theme this module's rate limiter previewed).