LRU Practice Problems

These four problems extend the basic LRU cache in directions that come up in interviews and in real code. Try each one before reading the approach. The solutions use OrderedDict to keep the focus on the idea; you can swap in the hand-written linked list from the implementation chapter.

Problem 1: Count the misses

A program issues a sequence of page requests, and memory holds k pages managed by LRU. Return the number of misses (page faults). Then find the smallest k for which the number of misses is at most a given limit.

Approach: simulate the cache once per capacity. Because LRU is a stack algorithm, misses never increase when k grows, so the smallest suitable k can be found with binary search over 1..number of distinct pages.

from collections import OrderedDict

def lru_misses(requests, k):
    cache, misses = OrderedDict(), 0
    for page in requests:
        if page in cache:
            cache.move_to_end(page)
        else:
            misses += 1
            cache[page] = True
            if len(cache) > k:
                cache.popitem(last=False)
    return misses

def smallest_capacity(requests, limit):
    lo, hi = 1, max(1, len(set(requests)))
    while lo < hi:
        mid = (lo + hi) // 2
        if lru_misses(requests, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

reqs = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4]
print(lru_misses(reqs, 3))         # 8
print(smallest_capacity(reqs, 7))  # 4

Problem 2: LRU with expiry

Extend the cache so that every entry also expires ttl seconds after it was written. An expired entry behaves like a missing one. The clock must be injectable so the cache can be tested without sleeping.

Approach: store (value, expires_at). Check the expiry on get and delete stale entries lazily. Capacity eviction still follows LRU order. Lazy expiry keeps both operations O(1); expired entries may occupy space until they are read or evicted, which is the same trade-off Redis makes alongside its active expiry cycle.

import time
from collections import OrderedDict

class TTLLRUCache:
    def __init__(self, capacity, ttl, clock=time.monotonic):
        self.capacity, self.ttl, self.clock = capacity, ttl, clock
        self.data = OrderedDict()            # key -> (value, expires_at)

    def get(self, key, default=None):
        item = self.data.get(key)
        if item is None:
            return default
        value, expires_at = item
        if self.clock() >= expires_at:
            del self.data[key]               # lazy expiry
            return default
        self.data.move_to_end(key)
        return value

    def put(self, key, value):
        self.data[key] = (value, self.clock() + self.ttl)
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

now = [0.0]
c = TTLLRUCache(2, ttl=10, clock=lambda: now[0])
c.put("a", 1)
now[0] = 5;  print(c.get("a"))   # 1
now[0] = 11; print(c.get("a"))   # None (expired)