Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 225 ยท Hashing

Designing an LRU Cache

Design an LRU cache with O(1) get and put in Python: dictionary plus doubly linked list, the OrderedDict shortcut, functools.lru_cache, and an O(1) LFU cache.

A cache is a small, fast store that keeps recent or popular results so you do not have to recompute or refetch them. Browsers cache images, databases cache pages, and your own code caches expensive function results. But a cache is small by definition, so when it is full and a new item arrives, something must be thrown out. The eviction policy decides what.

The most famous policy is LRU: Least Recently Used. Evict the item that has gone the longest without being touched. The idea rests on a good guess: things used recently are likely to be used again soon. Designing an LRU cache is also one of the most-asked interview problems, because it combines two structures you already know, a hash table and a doubly linked list, into something neither can do alone. In this lesson you will build it from scratch, then see the short Python versions, and finish with its sibling, the LFU cache.

The problem

Design a cache of fixed capacity with two operations, both in O(1) time:

  • get(key): return the value if present (and mark the key as most recently used), otherwise return -1 (or None).
  • put(key, value): insert or update the key and mark it most recently used. If this exceeds the capacity, first evict the least recently used key.
TEXT
capacity = 2
put(a,1)   order (old -> new): a
put(b,2)   order: a b
get(a)     order: b a          a becomes the newest
put(c,3)   full! evict b       order: a c
get(b)     -> miss

Brute force: a list of keys

The obvious design keeps entries in a list ordered from oldest to newest use. get must find the key in the list (O(n)), move it to the end (O(n)), and eviction removes the front (O(n) for a plain list). Every operation costs O(n).

Python Brute force LRU with a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Looking up the most recently used of 1,000 keys examines all 1,000 entries. We want that to be one step.

The key insight: two structures that cover for each other

We need two abilities at once:

  1. Find an entry by key in O(1). A dict does that.
  2. Reorder entries and remove the oldest in O(1). A doubly linked list does that, if you hold a direct reference to the node you want to move.

So combine them: the dict maps each key to its list node, and the list keeps nodes ordered by recency. The head side holds the most recent, the tail side the least recent.

TEXT
dict:   a -> [node a]   b -> [node b]   c -> [node c]

list (most recent -> least recent):

 HEAD <-> [c:3] <-> [a:1] <-> [b:2] <-> TAIL
 sentinel   newest                oldest  sentinel

get(b):  dict gives node b directly;
         unlink it (O(1) because it has prev/next), insert after HEAD.
evict:   take TAIL.prev (the oldest), unlink it, delete its key from the dict.

Two sentinel nodes (dummy head and tail) remove every edge case: there is always a node before and after any real node, so the unlink and insert code never checks for None.

Each node stores the key as well as the value. When you evict the tail node you need its key to delete the matching dictionary entry.

Implementation from scratch

Python LRU cache: dict plus doubly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace the third block: after get(1) the order is [1, 2] (most recent first). put(3, 30) finds the cache full, takes tail.prev which is key 2, unlinks it and deletes it from the dict, then inserts 3 at the front, giving [3, 1]. Every step is a constant number of pointer changes and dict operations, so get and put are O(1). Space is O(capacity).

Watch out: the order of pointer updates in _push_front matters. Set the new node's prev and next first, then fix the neighbors. Doing it in the wrong order loses the reference to the old first node and corrupts the list. Also remember to delete the evicted key from the dictionary; forgetting it leaves a stale entry pointing to an unlinked node.

The Python shortcut: OrderedDict

Python's collections.OrderedDict is itself a dictionary plus a linked list. It remembers insertion order and offers two O(1) methods that do exactly what we need: move_to_end(key) and popitem(last=False) (remove the oldest).

Python LRU with OrderedDict, compared with the linked version

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ordering is reversed compared with the linked version (here the end is the newest), but the behavior is identical. In an interview, write the from-scratch version unless the interviewer allows OrderedDict; in real code, the OrderedDict version is shorter and less bug-prone. A plain dict also keeps insertion order, so you can emulate this with d[key] = d.pop(key) (re-insert to move to the end) and next(iter(d)) (peek at the oldest), but OrderedDict states the intent clearly.

functools.lru_cache: caching function results

When what you want to cache is a function's results, the standard library already provides an LRU cache as a decorator. It is also the simplest way to add memoization.

Python functools.lru_cache and cache_info

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Things to know: arguments must be hashable (they become dictionary keys); maxsize=None never evicts; and decorating an instance method also caches on self, which keeps the object alive. Use it for pure functions whose results depend only on their arguments.

LFU: Least Frequently Used

LFU evicts the key that has been used the fewest times (breaking ties by evicting the least recently used among them). It suits workloads with a stable set of popular items, where a one-time scan of many items should not push out the favorites. LRU would flush the favorites during such a scan.

An O(1) LFU needs more bookkeeping:

  • values: key -> value and freq: key -> use count.
  • buckets: count -> OrderedDict of keys with that count, ordered by recency.
  • min_freq: the smallest count that currently has keys.

On each access the key moves from bucket c to bucket c + 1. If bucket min_freq becomes empty, min_freq increases by one. On eviction, remove the oldest key of bucket min_freq.

Python An O(1) LFU cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this tiny sequence an LRU cache would make the same choices. The policies diverge on longer workloads: if key 1 were read ten times and then 50 different one-off keys streamed through, LRU would evict key 1 while LFU would keep it.

Complexity summary

Design get put Space
List of keys (brute force) O(n) O(n) O(capacity)
Dict + doubly linked list O(1) O(1) O(capacity)
OrderedDict O(1) O(1) O(capacity)
LFU with frequency buckets O(1) O(1) O(capacity)

Beyond the interview

Real caches add concerns this lesson skipped: thread safety (wrap operations in a lock, or shard the cache), time-to-live expiry (store an expiry time per entry), size limits in bytes rather than item counts, and smarter admission policies (such as TinyLFU) that combine recency and frequency. The two-structure core, a hash map for lookup and a linked structure for ordering, stays the same.

Common mistakes

  • Forgetting to store the key in the node, so eviction cannot delete from the dict.
  • Not refreshing recency on put of an existing key. Updating a value is also a use.
  • Evicting before checking for an existing key, which removes an item when the update would have fit.
  • Breaking links with the wrong update order in the linked list; sentinels and careful ordering prevent it.
  • Using lru_cache on functions with unhashable arguments (lists, dicts), which raises TypeError.
  • Treating a miss and a stored value of -1 as the same when -1 is a legal value; return None or raise KeyError in real code.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does an O(1) LRU cache need both a dictionary and a doubly linked list?

    A dict alone cannot reorder by recency cheaply, and a list alone cannot find a key quickly. The dict points straight at the node and the doubly linked node can unlink itself in O(1).
  2. 2. capacity=2: put(1,a), put(2,b), get(1), put(3,c). Which key is evicted?

    After get(1), key 1 is the most recent, so key 2 is the least recently used when put(3,c) overflows the cache.
  3. 3. Why does each linked list node store its key as well as its value?

    Eviction starts from the list's tail node, so the node must know its own key in order to remove the dictionary entry that points to it.
  4. 4. Which OrderedDict calls implement 'mark most recent' and 'evict the oldest'?

    move_to_end moves a key to the newest end, and popitem(last=False) removes the entry at the oldest end. Both are O(1).
  5. 5. What is the main behavioral difference between LRU and LFU?

    LRU keeps what was touched most recently; LFU keeps what is touched most often, so a single scan of new items does not push out popular entries.

Summary

  • A cache has a fixed capacity and an eviction policy; LRU evicts the least recently used entry.
  • O(1) LRU = dictionary (key to node) plus doubly linked list ordered by recency, with sentinels and the key stored in each node.
  • OrderedDict with move_to_end and popitem(last=False) gives the same behavior in a few lines.
  • functools.lru_cache memoizes pure functions with LRU eviction; arguments must be hashable and cache_info() reports hits and misses.
  • LFU evicts the least frequently used key (ties by recency) and reaches O(1) using frequency buckets and a min_freq counter.

Next: Recursion