LRU Cache

Interview Prep

LegendaryLinked Listdesignlinked-listhashmap

The problem

Implement a fixed-capacity Least Recently Used cache with O(1) get(key) and put(key, value). On put, if the cache is at capacity, evict the least-recently-used key first. Both operations bump the touched key to "most recently used."

The challenge is the O(1) constraint. A list-only implementation is O(n) on every access. The standard answer pairs a hashmap (for constant-time lookup) with a doubly linked list (for constant-time reordering). Each map entry points at its node in the list; each list node carries its key so eviction can clean up the map.

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?"

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