“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

LRU Cache

Interview Prep

LegendaryLinked Listdesignlinked-listhashmap

The problem

Build a cache that holds at most N entries. get(key) returns the stored value; put(key, value) inserts or updates. When a put would exceed capacity, throw out the entry that has gone unused the longest. Reading a key or writing it both count as "using" it, and both operations must run in O(1).

Evicting whatever has sat unused the longest is a bet on temporal locality: things used recently tend to be used again soon. The bet has a mathematical backing — Sleator and Tarjan (1985) proved LRU is k-competitive: with a cache of size k it never suffers more than k times the misses of a clairvoyant strategy that knows the whole future. And the "use it or lose it" feeling is not a loose analogy: Anderson and Schooler (1991) showed human memory forgets on exactly this logic — recency of use is a strong statistical predictor of needing something again, so a memory that discards the stale is behaving rationally, not failing. Your brain runs an eviction policy; LRU is its two-line approximation.

The challenge is the O(1) constraint. A list-only implementation is O(n) on every access. The fix is to combine two structures, each covering the other's weakness. A hashmap jumps from a key straight to its value in O(1) on average (it computes an array index from the key — no scanning), but it keeps no usage order. A doubly linked list — nodes that each point to both neighbors — keeps perfect order and can unlink or relink any node in O(1) if you already hold a pointer to it, but finding a node by key means walking the list. Concretely: the map's value is not the cached data — it is a pointer to a list node, and the node holds the data plus a copy of its own key. Lookup goes map → node in one hop; "mark as recently used" is relinking that node to the front, O(1) in a doubly linked list. The key is duplicated inside the node for exactly one reason: eviction removes the list's tail node, and without the key stored there you could not find and erase the matching map entry.

Pattern: hashmap + doubly linked list

Recognize this any time the question pairs "fast lookup" with "ordered eviction" or "LRU/MRU/LFU." The two structures together give you both — neither alone does. The DLL gives O(1) move-to-front and O(1) tail removal; the hashmap gives O(1) "do you have this key?" And yes — this is a recurring move, worth naming: composite data structures, where each member repairs the other's weak operation. Java ships this exact pair as LinkedHashMap; LFU caches pair a map with frequency buckets; Dijkstra with decrease-key pairs a heap with a position map. When a problem demands two operations that no single structure does fast, try welding two together.

Solution — implement from scratch

class _Node:
    __slots__ = ('key', 'val', 'prev', 'nxt')

    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev: '_Node | None' = None
        self.nxt: '_Node | None' = None


class LRUCache:
    """O(1) get and put with capacity-bounded eviction.

    Two structures, joined at the hip:
      - dict[key]            → the node holding the value
      - doubly linked list   → recency order (head = most recent, tail = least)

    Sentinel head and tail nodes simplify edge handling: every real node
    has a non-None prev and nxt, so we never special-case "first" or "last".
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.map: dict[int, _Node] = {}
        self.head = _Node()
        self.tail = _Node()
        self.head.nxt = self.tail
        self.tail.prev = self.head

    # --- linked-list primitives -----------------------------------------

    def _detach(self, node: _Node) -> None:
        node.prev.nxt = node.nxt
        node.nxt.prev = node.prev

    def _push_front(self, node: _Node) -> None:
        node.prev = self.head
        node.nxt = self.head.nxt
        self.head.nxt.prev = node
        self.head.nxt = node

    # --- public API -----------------------------------------------------

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._detach(node)
        self._push_front(node)        # mark as most-recently used
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.val = value
            self._detach(node)
            self._push_front(node)
            return

        if len(self.map) == self.cap:
            evict = self.tail.prev    # least-recently used
            self._detach(evict)
            del self.map[evict.key]

        node = _Node(key, value)
        self._push_front(node)
        self.map[key] = node

O(1) per operation, O(capacity) space. The sentinel head and tail nodes are the secret weapon — they let every "remove" and "insert" use the same code path, no special-casing for the empty list or the single-element list.

The two helpers _detach and _push_front are deliberately tiny. get and put read almost like prose: detach, push to front, update map. Memorise the skeleton — interviewers love this problem for the chance to see whether you write clean pointer code.

Solution — using OrderedDict

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key, last=False)   # most recent at front
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key, last=False)
        elif len(self.cache) == self.cap:
            self.cache.popitem(last=True)         # evict least recent
        self.cache[key] = value
        self.cache.move_to_end(key, last=False)

Same big-O. OrderedDict.move_to_end and popitem are amortised O(1). Acceptable in some interviews, weak in others — most interviewers want to see the DLL+map version because it demonstrates you understand why OrderedDict is O(1).

Walkthrough

cap = 2

put(1, 1)        list: [1]            map: {1}
put(2, 2)        list: [2, 1]         map: {1, 2}
get(1) → 1       list: [1, 2]         (1 is now most recent)
put(3, 3)        list: [3, 1]         (2 evicted)        map: {1, 3}
get(2) → -1                           (already evicted)
put(4, 4)        list: [4, 3]         (1 evicted)        map: {3, 4}
get(1) → -1
get(3) → 3       list: [3, 4]
get(4) → 4       list: [4, 3]

Edge cases

Related