This problem follows the Hash Map + Doubly Linked List pattern, commonly found in the Linked List category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Hash map for O(1) lookup. Doubly linked list for O(1) move-to-front and eviction.
The hash map gives O(1) lookup, the doubly linked list gives O(1) reordering — together they make both get and put O(1).
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {} # key -> node
self.head, self.tail = Node(0,0), Node(0,0)
self.head.next, self.tail.prev = self.tail, self.head
def get(self, key):
if key in self.map:
self._moveToFront(self.map[key])
return self.map[key].val
return -1
def put(self, key, val):
if key in self.map:
self.map[key].val = val
self._moveToFront(self.map[key])
else:
node = Node(key, val)
self.map[key] = node
self._addToFront(node)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]Practice LRU Cache and similar Linked List problems with flashcards. Build pattern recognition through active recall.
Practice this problem