Medium Hash + DLL Linked Lists
In plain English: Build a cache with a fixed capacity. When full, evict the least recently used item. Both get and put should be O(1).
Combine a hash map (O(1) lookup) with a doubly linked list (O(1) removal and insertion). The list maintains usage order — most recent at head, least recent at tail. On access, move to head; on eviction, remove from tail.
Prompt
Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement get(key) and put(key, value) in O(1) time.
Try to write it from scratch before scrolling down.
Solution
class DLLNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {}
self.head = DLLNode() # dummy head
self.tail = DLLNode() # dummy tail
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_front(node) # mark as recently used
return node.val
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = DLLNode(key, value)
self._add_front(node)
self.cache[key] = node
if len(self.cache) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
# Test: c = LRUCache(2)
# c.put(1,1); c.put(2,2); c.get(1) == 1
# c.put(3,3); c.get(2) == -1 (evicted)