Design and implement an LRU cache with O(1) get and put

TL;DR: A hashmap plus a doubly linked list with sentinel head/tail gives O(1) get/put; OrderedDict.move_to_end is the interview-legal shortcut, so offer both and read the room.

How to approach it State the two requirements and the structure they force: O(1) lookup needs a hashmap; O(1) recency update and eviction needs a doubly linked list; the classic answer glues them together. Then make the move that reads senior: "Python's OrderedDict is that combination. I can give you a correct version in ten lines, or build the linked list from scratch. Which would you like?" Most interviewers say "OrderedDict first, then from scratch," and you've just demonstrated both pragmatism and depth.

A strong answer The pragmatic version:

from collections import OrderedDict

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

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

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

The from-scratch version is a dict mapping key to node, plus a doubly linked list with sentinel head/tail so insert/remove have no None-checks. The map points at nodes; the list orders them by recency:

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 LRU:
    def __init__(self, capacity: int):
        self.cap, self.map = capacity, {}
        self.head, self.tail = Node(), Node()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, n):  n.prev.next, n.next.prev = n.next, n.prev
    def _add_front(self, n):
        n.next, n.prev = self.head.next, self.head
        self.head.next.prev = n; self.head.next = n

    def get(self, key):
        if key not in self.map: return -1
        n = self.map[key]; self._remove(n); self._add_front(n)
        return n.val

    def put(self, key, val):
        if key in self.map: self._remove(self.map[key])
        n = Node(key, val); self.map[key] = n; self._add_front(n)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru); del self.map[lru.key]   # node stores key for this
    

Narrate the two classic traps as features: nodes store their key so eviction can delete from the map, and sentinels eliminate every edge case at the ends. The first trap deserves proof, because the buggy version passes a casual test: we ran an LRU whose eviction removes the node from the list but not the map (the natural bug when nodes don't carry their key), and after 10 puts into a capacity-2 cache, the map held all 10 entries. Nothing crashed. get on recent keys works, eviction order looks right from the list's perspective, and the cache is silently unbounded, a memory leak wearing a passing test suite, plus a correctness bug lurking behind it (a "evicted" key found in the map returns a node the list no longer orders). That is why the eviction test below checks get(2) == -1 explicitly, and why in review you look for del self.map[...] inside eviction before anything else. Test eviction order explicitly.

c = LRU(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1          # 1 is now most recent
c.put(3, 3)                   # evicts 2, not 1
assert c.get(2) == -1 and c.get(1) == 1 and c.get(3) == 3
c.put(1, 99)                  # update refreshes recency
assert c.get(1) == 99

What interviewers probe next (1) TTL per entry? Store expiry timestamps, check lazily on get; this is the bridge to the in-memory-database question. (2) Thread safety? One lock around both ops; get mutates recency, so a read-write lock doesn't help, and saying that wins points. (3) LFU? Different structure (count buckets); recognize, don't improvise it. (4) Real systems? Mention functools.lru_cache and that Redis approximates LRU by sampling, which is production texture.

Common mistakes Forgetting get mutates recency order. Evicting from the list but not the map (the missing-key-on-node bug). put on an existing key not refreshing recency. Using a singly linked list and discovering removal needs the predecessor. And building from scratch unprompted when offering the choice was the stronger move.

Key takeaways

• Hashmap for O(1) lookup, doubly linked list for O(1) recency reorder and eviction.
• Sentinel head/tail nodes erase the empty-list and single-element pointer edge cases.
• Each node stores its key so eviction can delete the entry from the map.
• Offer OrderedDict.move_to_end first, then build from scratch only if asked.