Lab 01 — LRU Cache

Goal

Implement a thread-unsafe and a thread-safe LRUCache with O(1) get and put, using a doubly-linked list keyed by a hashmap. After this lab you should be able to write a clean, tested LRU cache from a blank screen in under 20 minutes, and answer the 13 standard follow-ups for it crisply.

Background Concepts

A cache is a bounded-capacity associative store that evicts entries when capacity is exceeded. The Least Recently Used (LRU) policy evicts whichever entry was accessed (read or written) the furthest in the past. The reason this is the canonical practical-coding warmup is that both O(1) operations require coordinating two data structures: a hashmap that maps keys to nodes (so get is O(1)), and a doubly-linked list ordered by recency (so eviction and recency-update are O(1)). Either structure alone forces an O(N) operation. That two-structure coordination is the engineering insight the interviewer wants to see.

The doubly-linked list uses sentinel head and tail nodes — this avoids null checks at the ends and reduces the function body from a tangle of if-statements to four pointer assignments per operation.

Interview Context

LRU cache is asked at almost every senior coding interview at Big Tech, Stripe, Uber, and Cloudflare. It is LeetCode 146 verbatim, but the bar at the practical-engineering level is far higher than passing the LeetCode test cases: you must produce production-shaped code (encapsulation, naming, error handling, optional thread-safety) and answer follow-ups about concurrency, persistence, sharding, and observability. Failing to articulate any of those follow-ups crisply is a common no-hire signal even when the algorithm is correct.

Problem Statement

Design a class LRUCache(capacity) supporting:

  • get(key) -> value or None — return the value for key, marking the entry as most-recently-used. Return None (or sentinel) if not present.
  • put(key, value) — insert or update. If the cache exceeds capacity, evict the least-recently-used entry.

Both operations must run in O(1) average time.

Constraints

  • 1 ≤ capacity ≤ 10^5
  • Keys are hashable; values are arbitrary
  • get and put may be called up to 10^7 times in benchmarks
  • Thread-safe variant: any number of concurrent callers

Clarifying Questions

  1. Are keys always hashable, or can they be raw bytes / mutable objects? (Assume hashable.)
  2. Does put of an existing key count as a “use” for LRU ordering? (Yes — by convention.)
  3. Is the API allowed to return a sentinel for missing keys, or must it raise? (Both are defensible; pick one and document.)
  4. Must the cache be thread-safe? (Often “we’ll get to that” — write the single-threaded version first, then add a lock when asked.)
  5. Eviction callback (notify on evict) needed? (Often a follow-up; design so it can be added without changing the call sites.)

Examples

cache = LRUCache(2)
cache.put(1, "a")              # state: [1]
cache.put(2, "b")              # state: [2, 1]
cache.get(1)        -> "a"     # state: [1, 2]
cache.put(3, "c")              # evict 2; state: [3, 1]
cache.get(2)        -> None
cache.put(1, "z")              # update; state: [1, 3]
cache.get(3)        -> "c"     # state: [3, 1]

Initial Brute Force

A dict plus a list that records the access order. Each get does a linear scan to remove and re-append the key. O(N) per op.

class LRUCacheBrute:
    def __init__(self, cap):
        self.cap = cap
        self.store = {}
        self.order = []   # least-recent at front

    def get(self, k):
        if k not in self.store: return None
        self.order.remove(k); self.order.append(k)
        return self.store[k]

    def put(self, k, v):
        if k in self.store:
            self.order.remove(k)
        elif len(self.store) >= self.cap:
            old = self.order.pop(0)
            del self.store[old]
        self.store[k] = v; self.order.append(k)

Brute Force Complexity

O(N) per get / put because list.remove and list.pop(0) are O(N). At N=10^5 with 10^7 calls, this is 10^12 operations — it will not finish.

Optimization Path

Replace the order-tracking list with a doubly-linked list, and add a hashmap that maps each key to its node. Now removal and append are O(1), so each operation is O(1). The hashmap uses ~3x more memory than the brute, which is the standard space-time tradeoff and is acceptable.

Final Expected Approach

  • Node: (key, value, prev, next). Storing the key in the node is essential — when we evict the LRU node, we need its key to remove it from the hashmap.
  • Sentinels: head (most recent) and tail (least recent) sentinel nodes that always exist. Real nodes live between them.
  • _add_after_head(node): insert immediately after head.
  • _remove(node): splice out by relinking neighbors.
  • _touch(node): remove + add after head. This is the recency update.
  • get(k): hashmap lookup → if hit, _touch(node) and return value; else None.
  • put(k, v): if exists, update value and _touch; else create node, _add_after_head, hashmap insert, evict if over capacity (the node before tail).

Data Structures Used

StructurePurpose
dictkey → node lookup, O(1)
Doubly-linked list (with sentinels)recency ordering, O(1) splice
RLock (thread-safe variant)guards both structures together

Correctness Argument

The invariants we maintain after every get or put:

  1. The hashmap and the linked list contain exactly the same set of keys.
  2. The list size never exceeds capacity.
  3. The node immediately after head was the most-recently accessed; the node immediately before tail is the LRU candidate.

Each of get, put, _touch, _remove, _add_after_head preserves all three invariants by inspection of the four pointer assignments per splice. The eviction step in put is the only place that may shrink both structures; it removes exactly one node from both, by reading its key from the node before deleting from the hashmap.

Complexity

  • get: O(1) average (hashmap lookup + 4 pointer writes)
  • put: O(1) average
  • Space: O(capacity)

Implementation Requirements

A complete working implementation is required. Below is the canonical Python version with thread-safety and a clean separation between the storage (the linked list + hashmap) and the policy (eviction order). Tests are required.

import threading
from typing import Hashable, Any, Optional

class _Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=None, val=None):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    """Thread-safe O(1) LRU cache.

    Concurrency: a single RLock guards both the hashmap and the linked list.
    The locked region is short (constant pointer work), so contention is low
    until very high concurrency. For higher concurrency, see follow-up #1.
    """

    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._cap = capacity
        self._map: dict[Hashable, _Node] = {}
        self._head, self._tail = _Node(), _Node()
        self._head.next = self._tail
        self._tail.prev = self._head
        self._lock = threading.RLock()

    def get(self, key: Hashable) -> Optional[Any]:
        with self._lock:
            node = self._map.get(key)
            if node is None:
                return None
            self._touch(node)
            return node.val

    def put(self, key: Hashable, value: Any) -> None:
        with self._lock:
            node = self._map.get(key)
            if node is not None:
                node.val = value
                self._touch(node)
                return
            node = _Node(key, value)
            self._map[key] = node
            self._add_after_head(node)
            if len(self._map) > self._cap:
                lru = self._tail.prev
                self._remove(lru)
                del self._map[lru.key]

    def __len__(self) -> int:
        with self._lock:
            return len(self._map)

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

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

    def _touch(self, node: _Node) -> None:
        self._remove(node)
        self._add_after_head(node)

Tests

Required: unit tests for the contract, smoke tests for ordering, concurrency tests for the thread-safe variant.

import unittest, threading, random

class TestLRU(unittest.TestCase):
    def test_basic(self):
        c = LRUCache(2)
        c.put(1, "a"); c.put(2, "b")
        self.assertEqual(c.get(1), "a")
        c.put(3, "c")                          # evicts 2
        self.assertIsNone(c.get(2))
        self.assertEqual(c.get(3), "c")
        self.assertEqual(c.get(1), "a")

    def test_update_is_a_use(self):
        c = LRUCache(2)
        c.put(1, "a"); c.put(2, "b"); c.put(1, "z")
        c.put(3, "c")                          # evicts 2 (1 was just updated)
        self.assertEqual(c.get(1), "z")
        self.assertIsNone(c.get(2))

    def test_capacity_one(self):
        c = LRUCache(1)
        c.put(1, "a"); c.put(2, "b")
        self.assertIsNone(c.get(1))
        self.assertEqual(c.get(2), "b")

    def test_concurrent(self):
        c = LRUCache(100)
        def worker():
            for _ in range(10000):
                k = random.randint(0, 200)
                if random.random() < 0.5:
                    c.put(k, k * 2)
                else:
                    c.get(k)
        threads = [threading.Thread(target=worker) for _ in range(8)]
        for t in threads: t.start()
        for t in threads: t.join()
        self.assertLessEqual(len(c), 100)      # invariant: never over capacity

Follow-up Questions

(1) How would you make it thread-safe? Already shown: a single RLock around the body of every public method. The lock is held only for O(1) work, so contention is bounded. For higher concurrency, shard by hash(key) % N into N independent caches; this is the practical answer for production caches at high QPS. A lock-free LRU is hard and rarely worth it.

(2) How would you persist state across restarts? Snapshot the cache to disk on a configurable interval (write the (key, value, recency-rank) triples in LRU order). On restart, replay the file in order. For stricter durability, write a per-put log entry to a write-ahead log; on restart, replay snapshot + log. Note: most caches choose not to persist — losing the cache on restart is usually fine, and persistence adds complexity for small benefit.

(4) How would you observe and monitor it? Emit hit-rate (hits / (hits + misses)) as a gauge; emit eviction count as a counter; emit cache size as a gauge; emit get/put latency as a histogram. Hit rate is the #1 actionable signal. Set an alert on hit rate dropping below the SLO.

(7) How would you handle backpressure? Caches don’t have classical backpressure since there’s no producer queue, but the analog is memory pressure: if the host is short on memory, the cache should shed load. Either (a) a soft size_in_bytes ceiling that triggers eviction beyond capacity, or (b) integrate with a host-level memory pressure signal (cgroup memory accounting on Linux). Decide explicitly which.

(11) What configuration knobs would you expose? capacity (entries), optionally size_bytes (RAM ceiling), optionally eviction_callback. Knobs not to expose: lock granularity, internal data structure choice, snapshot interval (set sensible default and document).

(12) What is the shutdown / draining behavior? The cache itself is in-memory and stateless from the caller’s perspective; on shutdown, optionally write a snapshot, then release the lock and let GC reclaim. No draining required; no in-flight work to finish.

Product Extension

LRU caches are the workhorse of CDN edge caches, database query result caches (Redis with allkeys-lru), HTTP reverse proxies, and database buffer pools. Real-world variants: two-level cache (L1 in-process + L2 Redis); size-aware LRU (counts bytes, not entries); adaptive LRU/LFU hybrid (ARC, used by ZFS). The data structure you wrote here is the textbook foundation; the variants tune it for specific workloads.

Language/Runtime Follow-ups

  • Python: collections.OrderedDict already implements LRU semantics — move_to_end() for _touch, popitem(last=False) for evict. In an interview, state that you know OrderedDict exists, then implement from scratch because the interviewer wants to see the linked list. Production: prefer OrderedDict or functools.lru_cache (decorator) unless you need eviction callbacks.
  • Java: LinkedHashMap with accessOrder=true and an overridden removeEldestEntry is the textbook Java LRU. For thread-safety wrap with Collections.synchronizedMap, or use Caffeine (Guava successor) which is O(1) and concurrent.
  • Go: no stdlib LRU; the container/list package gives a linked list, and a map[K]*list.Element gives O(1) lookup. The hashicorp/golang-lru package is the de facto standard in production Go.
  • C++: std::list<std::pair<K,V>> plus std::unordered_map<K, list::iterator>. Iterator stability of std::list is the reason this works.
  • JS/TS: Map preserves insertion order, so map.delete(k); map.set(k, v) is the recency-update pattern. Eviction is map.delete(map.keys().next().value). This works because Map.prototype.keys() returns keys in insertion order.

Common Bugs

  1. Forgetting to update the hashmap when evicting (only removing from the linked list). The next get for the evicted key returns a dangling node. The fix is to read the node’s key before unlinking and use it to delete from the hashmap.
  2. Storing only the value (not the key) in the node, then having no way to find the hashmap entry to delete on eviction.
  3. Calling _touch before checking whether the key exists — touches a None.
  4. In the thread-safe variant, taking the lock in get but not in put, or releasing between the eviction step and the insert step. The whole operation must be atomic.
  5. Using a non-reentrant Lock and then calling another locked method internally — deadlock. Use RLock if you need to call locked methods from inside a locked method.

Debugging Strategy

If get returns the wrong value: print [(n.key, n.val) for n in walk(self._head)] after each put, compare to the expected access order. If the cache exceeds capacity: assert len(self._map) <= self._cap after every put; the violation tells you which call broke the invariant. For concurrency bugs (rare under the single-lock design), run the concurrent test with pytest --count=1000 until a failure repros, then add print(threading.get_ident(), op, key) traces and minimize.

Mastery Criteria

  • Implemented LRUCache with sentinel head/tail in <15 minutes from blank screen.
  • All four tests pass on first run.
  • Articulated invariants (hashmap-list set equality, capacity bound, head/tail recency) without prompting.
  • Stated O(1) time and O(capacity) space unprompted.
  • Answered follow-ups #1, #4, #7, #11, #12 in <90 seconds each, naming alternatives.
  • Refactored a single-threaded version into the thread-safe version in <5 minutes.