LRU Cache

Design a data structure that supports get and put in O(1) time with an eviction policy: when capacity is exceeded, the least recently used key is dropped. The machine must track both a fast key lookup and a global recency ordering simultaneously.

The key insight: no single structure does both. A hash map gives O(1) lookup but no ordering; a doubly linked list gives O(1) removal and insertion at known positions but no lookup. Pair them: the map stores key → node, and the linked list holds key-value pairs in recency order. The doubly linked list matters because removing a middle node requires knowing its predecessor — only a doubly linked list gives that in O(1).

Approach:

1. Keep dict[key] -> node plus a doubly linked list with dummy head/tail sentinels.
2. get: if key exists, move its node to the tail (most recent) and return the value.
3. put: if key exists, update it; else insert at the tail; if over capacity, pop the head (least recent) and delete its key from the map.

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head
 
    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
 
    def _add(self, node):
        node.prev, node.next = self.tail.prev, self.tail
        self.tail.prev.next = node
        self.tail.prev = node

Time: O(1) per operation. Space: O(capacity).

Trickiest edge case: put on an existing key does not count as an insertion — it must move the node to the tail and must not double-evict.