LRU Cache Design

A cache is a small, fast store that holds a subset of some larger, slower dataset. Because it's small, it eventually fills up, and then you must decide what to throw out to make room. LRU — least recently used — is the most common rule: evict whatever you haven't touched for the longest time, on the bet that recently-used things are the most likely to be used again. The design challenge, and the reason this is such a beloved interview question, is doing all of it — lookup, insert, and eviction — in $O(1)$ time.

Why two data structures

Neither obvious choice works alone. A plain hash map gives $O(1)$ lookup but knows nothing about order of use, so finding the least-recently-used item means scanning everything — $O(n)$. A plain list keeps order but lookup is $O(n)$. The trick is to combine them:

• A hash map from key to a node, for $O(1)$ lookup.
• A doubly linked list of those nodes, ordered most-recent at the front, least-recent at the back. Because it's doubly linked, you can unlink any node and splice it to the front in $O(1)$ — no shifting.

Every access does two things: look up the node through the map, then move it to the front of the list. Eviction is just "drop the node at the back and delete its key from the map."

Worked example: capacity 2

Start with an empty cache of capacity 2 and run this sequence. The list is written front (most recent) to back:

Operation	Result	Cache state (front → back)
put(1, A)	—	1
put(2, B)	—	2, 1
get(1)	A	1, 2
put(3, C)	evicts 2	3, 1
get(2)	miss	3, 1

Watch the crucial move: get(1) doesn't just return a value, it also promotes key 1 to the front. So when put(3, C) needs room, the least-recently-used key is 2, not 1 — and 2 is the one evicted. A later get(2) therefore misses.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()      # remembers insertion / move order
        self.cap = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)     # mark as most-recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)   # evict least-recently used

Python's OrderedDict is a hash map backed by a doubly linked list — exactly the structure above — so move_to_end and popitem(last=False) are the $O(1)$ operations. In a language without it, or when the interviewer asks you to "build it from scratch," you wire the map and the linked list together by hand.

Where it shows up in quant-dev interviews

"Design an LRU cache" is a rite of passage at quant and HFT shops because caching is everywhere on a low-latency desk: caching computed prices, memoizing expensive risk calculations, and holding hot market-data snapshots so you don't recompute them tick after tick. The follow-ups probe your data-structure judgment — make it thread-safe, add a time-to-live so stale quotes expire, or switch the policy to LFU (least frequently used). Each variant tests whether you actually understand why the map-plus-list pairing gives $O(1)$, rather than having memorized one answer.

The pattern generalizes: any time you need both fast lookup and fast ordered eviction, reach for a hash map paired with an order-keeping structure — the same instinct behind an Order Book Data Structure and a rolling Median from a Data Stream.