Least Recently Used Cache
Problem
Build a fixed-size cache for an API gateway. LRUCache(capacity) creates it; get(key) returns the stored value, or -1 if the key is missing; put(key, value) inserts or updates a key. Both calls count as a use of the key. When a put would push the cache past its capacity, first evict the key that was used longest ago. Both operations must run in O(1) time, and the capacity is between 1 and 3,000. Build the ordering yourself with a doubly linked list instead of using OrderedDict.
Examples
Input: capacity = 2
put(1, 1), put(2, 2), get(1), put(3, 3), get(2), put(4, 4), get(1), get(3), get(4)
Output: [1, -1, -1, 3, 4]
Why: put(3, 3) evicts 2 because get(1) just used 1; put(4, 4) then evicts 1Input: capacity = 2
put(1, 1), put(2, 2), put(1, 10), put(3, 3), get(1), get(2)
Output: [10, -1]
Why: updating key 1 also counts as a use, so key 2 is the one evictedInput: capacity = 1
put(1, 1), put(2, 2), get(1), get(2)
Output: [-1, 2]
Why: edge case, every new key evicts the only one storedHints
0 / 3
A dictionary finds a key in O(1), but it cannot tell you which key was used longest ago. You need a second structure that keeps keys in order of use.
Keep the entries in a doubly linked list, most recent at the front. Because each node knows both of its neighbours, it can be cut out and moved to the front in O(1) once the dictionary hands it to you.
Use two sentinel nodes, a head and a tail that never hold data, so unlinking and inserting never have to check for an empty list. The node just before the tail sentinel is the one to evict.
Solution
The cache needs two things in constant time: finding a key, and knowing which key is the stalest. A dictionary from key to list node handles the first, and a doubly linked list ordered by use handles the second. Every get or put moves the key's node to the front, which is O(1) because the node knows its own neighbours and can be spliced out without a search. Eviction removes the node just before the tail sentinel and deletes its key from the dictionary, which is why each node stores its key as well as its value. The head and tail sentinels are permanent, so every real node always has both neighbours and no pointer update needs a special case. Each operation is O(1), and space is O(capacity).
class Node:
def __init__(self, key=0, val=0):
self.key, self.val, self.prev, self.next = key, val, None, None
class LRUCache:
def __init__(self, capacity):
self.capacity, self.nodes = capacity, {}
self.head, self.tail = Node(), Node() # sentinels, never evicted
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
self._unlink(node)
self._push_front(node) # now the most recent
return node.val
def put(self, key, val):
if key in self.nodes:
node = self.nodes[key]
node.val = val
self._unlink(node)
else:
if len(self.nodes) == self.capacity:
stalest = self.tail.prev
self._unlink(stalest)
del self.nodes[stalest.key]
node = self.nodes[key] = Node(key, val)
self._push_front(node)
def run(capacity, ops):
cache, out = LRUCache(capacity), []
for op in ops:
if op[0] == "put":
cache.put(op[1], op[2])
else:
out.append(cache.get(op[1]))
return out
first = [("put", 1, 1), ("put", 2, 2), ("get", 1), ("put", 3, 3), ("get", 2),
("put", 4, 4), ("get", 1), ("get", 3), ("get", 4)]
second = [("put", 1, 1), ("put", 2, 2), ("put", 1, 10), ("put", 3, 3), ("get", 1), ("get", 2)]
third = [("put", 1, 1), ("put", 2, 2), ("get", 1), ("get", 2)]
print(run(2, first)) # -> [1, -1, -1, 3, 4]
print(run(2, second)) # -> [10, -1]
print(run(1, third)) # -> [-1, 2]Stuck on the idea rather than the code? Doubly Linked Lists covers it.