Coding-Round Walkthroughs & Method¶

from collections import OrderedDict

class LRUCache:
    """O(1) get and put using Python's OrderedDict (doubly-linked list + hash map).

    Narration: "I'll use OrderedDict which maintains insertion order.
    The most-recently-used key lives at the right (last). When I access
    a key I move it to the right; when capacity is exceeded I pop from
    the left (the LRU end)."
    """
    def __init__(self, capacity: int) -> None:
        self.capacity = 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)   # mark as most recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict LRU (the leftmost item)

# ── inline test (do this during the interview) ────────────────────────────
lru = LRUCache(2)
lru.put(1, 1)          # cache: {1:1}
lru.put(2, 2)          # cache: {1:1, 2:2}
assert lru.get(1) == 1 # cache: {2:2, 1:1} — 1 is now most recent
lru.put(3, 3)          # evicts key 2; cache: {1:1, 3:3}
assert lru.get(2) == -1
lru.put(4, 4)          # evicts key 1; cache: {3:3, 4:4}
assert lru.get(1) == -1
assert lru.get(3) == 3
assert lru.get(4) == 4
print("LRU tests passed")

"""Manual doubly-linked list + hash map — show this if asked to go deeper."""

class DLNode:
    def __init__(self, key: int = 0, val: int = 0) -> None:
        self.key = key; self.val = val
        self.prev: 'DLNode | None' = None
        self.next: 'DLNode | None' = None

class LRUCacheManual:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.map: dict[int, DLNode] = {}
        # sentinel head (LRU end) and tail (MRU end) simplify edge cases
        self.head = DLNode(); self.tail = DLNode()
        self.head.next = self.tail; self.tail.prev = self.head

    def _remove(self, node: DLNode) -> None:
        node.prev.next = node.next      # type: ignore[union-attr]
        node.next.prev = node.prev      # type: ignore[union-attr]

    def _insert_at_tail(self, node: DLNode) -> None:
        prev = self.tail.prev
        prev.next = node                # type: ignore[union-attr]
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._insert_at_tail(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = DLNode(key, value)
        self.map[key] = node
        self._insert_at_tail(node)
        if len(self.map) > self.cap:
            lru = self.head.next        # leftmost real node
            self._remove(lru)           # type: ignore[arg-type]
            del self.map[lru.key]       # type: ignore[union-attr]