# Designing an LRU cache that actually runs in O(1)

Source: https://www.techinterview.org/post/3233476035/lru-cache-design-o1/
Updated: 2026-07-02 · techinterview.org

LeetCode 146 reads easy until you hit one line in the spec: both `get` and `put` have to run in O(1) average time. That single constraint rules out almost every structure you'd reach for first, and it's the reason the problem keeps getting asked. Amazon, Bloomberg, Microsoft, and Twitch have all run it as a 30-to-40-minute screen, because it cleanly separates someone who memorized an answer from someone who can explain why the answer has the shape it does.

The rules are short. You build a cache with a fixed `capacity`. `get(key)` returns the value or -1 if the key is absent. `put(key, value)` inserts or overwrites, and if that pushes the size over capacity, you evict the least recently used entry. Every `get` and every `put` counts as a use, so the recency order shifts constantly. With as many as 200,000 calls in the test set, an O(n) operation hiding anywhere times out.

## Why the obvious structures fail

Start with a plain hash map. Lookup is O(1), which handles half the problem, but a map has no notion of order, so when you need to evict you have no idea which key was used longest ago. Bolt a timestamp onto each entry and eviction becomes a full scan for the minimum, O(n) every time the cache fills up.

Try an array or Python list where you move each accessed item to the end. Eviction from the front gets cheap, but finding the item to move is a linear search, and shifting elements is O(n) too. A singly linked list has the opposite problem: you can hold a pointer to a node, but to unlink it you need its predecessor, and finding that predecessor walks the list. Every single-structure answer trips over the same wall. One structure gives you fast lookup, a different one gives you fast reordering, and the problem wants both at once.

## Hash map paired with a doubly linked list

The answer is to run two structures together and keep them pointing at the same nodes. A hash map takes you from a key to a node in O(1). A doubly linked list holds those nodes in recency order, most recently used at one end, least recently used at the other. Because the list is doubly linked, once the map hands you a node you can splice it out in constant time by rewiring its two neighbors, no traversal needed.

Reads and writes both become a small dance. On `get`, look up the node, unlink it from wherever it sits, and reinsert it at the most-recently-used end. On `put` for a key already present, overwrite the value and do the same move. On `put` for a new key past capacity, drop the node at the least-recently-used end, delete its key from the map, then insert the newcomer at the front. The map keeps lookups flat; the list keeps ordering flat.

## Sentinel nodes remove the edge cases

The bugs in this problem almost all live at the ends of the list: removing the only node, inserting into an empty list, evicting the tail when the tail is also the head. You can write null checks for each, or you can make them vanish by allocating two dummy nodes, a permanent head and a permanent tail, that never hold data. Every real node lives between them. Now "insert at front" and "remove a node" are the same handful of pointer assignments no matter what, and you stop reasoning about emptiness at all.


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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.store = {}                 # key -> Node
        self.head = Node()              # sentinel on the most-recent side
        self.tail = Node()              # sentinel on the least-recent side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

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

    def get(self, key: int) -> int:
        node = self.store.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.store.get(key)
        if node is not None:
            node.val = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.store) == self.cap:
            lru = self.tail.prev
            self._unlink(lru)
            del self.store[lru.key]
        node = Node(key, value)
        self.store[key] = node
        self._push_front(node)
```


Every path here is constant time. The `__slots__` line is a small touch that cuts per-node memory and speeds up attribute access; say it out loud and a sharp interviewer clocks that you've thought about the constant factors, not only the big-O.

## Where candidates lose the round

The most common miss is treating `put` on an existing key as a pure value update and forgetting it counts as a use. Skip the reorder and your recency order drifts wrong, and the bug only surfaces several operations later when the wrong key gets evicted. Right behind it is forgetting to delete the evicted key from the map. The list shrinks, the map doesn't, and you've built a slow memory leak that also hands back stale nodes.

A few more that interviewers watch for: returning the node instead of `node.val`; using a falsy check like `if not node` when a stored value could be 0, which is why the code above tests `is None`; and writing the capacity check with `>` instead of `==` so the cache briefly holds one item too many. None of these are conceptual, but a clean run without them is part of what's being scored. Talk through the eviction case before you write it, because that's where the pointer juggling bites.

## OrderedDict and LinkedHashMap, and when the shortcut is fair game

Both Python and Java ship a structure that already does this. Python's `collections.OrderedDict` gives you `move_to_end(key)` and `popitem(last=False)`, which is the whole problem in two method calls. Java's `LinkedHashMap` takes an `accessOrder=true` flag and an overridable `removeEldestEntry`, and it was practically built for this.

Whether you can use them depends on what's being tested. If the prompt is "design an LRU cache," most interviewers want the hand-rolled version, because the doubly linked list reasoning is the point. A strong move is to say you'd reach for `OrderedDict` in real code, then offer to implement it from scratch to show the mechanics. That signals you know the standard library without hiding behind it. If the round is about a larger system and the cache is one component, nobody cares; use the built-in and keep moving.

| Approach | get | put / evict | Use it when |
| --- | --- | --- | --- |
| Hash map + per-entry timestamp | O(1) | O(n) evict | Never, on this problem |
| Hash map + doubly linked list | O(1) | O(1) | The interview answer |
| OrderedDict / LinkedHashMap | O(1) | O(1) | Real code, or when allowed |

## LFU, TTL, and what production actually runs

Once your LRU works, the follow-up usually swaps the eviction policy. LFU, LeetCode 460, evicts the least frequently used key and is a real step up: you track a use count per key, group keys by count, and keep a pointer to the current minimum frequency so eviction stays O(1). The clean build is a map from key to node, a second map from frequency to a doubly linked list of keys at that frequency, and a running `min_freq`. Ties inside a frequency break by recency, so each bucket is itself an LRU list. People who breeze through 146 often stall here, which is exactly why it's the follow-up.

TTL is the other common twist. Add an expiry timestamp per entry and a key can die of old age before it ever becomes the least recently used, so reads have to check expiry and you need a way to reclaim dead entries without scanning everything, usually a lazy check on access plus a background sweep. Then someone asks about concurrency, and the catch is that a single lock around the whole structure serializes every request and wrecks throughput, so real caches shard the keyspace and lock per shard.

The textbook LRU you just wrote is rarely what ships, and saying so is worth real points. Maintaining a perfectly ordered list on every access costs too much under heavy load, so Redis approximates: with `maxmemory-policy allkeys-lru` it samples a handful of random keys and evicts the oldest of that sample rather than the true global oldest. Database buffer pools lean on CLOCK or segmented LRU for the same reason, and policies like ARC try to balance recency against frequency. Naming that gap, that exact LRU is a teaching structure and production caches trade a little accuracy for a lot of speed, is often the difference between an answer that's correct and one that sounds like it came from someone who has run a cache in anger.