LRU Cache
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Build a cache with get and put in O(1) that throws away the least recently used entry when it is full.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1A dictionary finds an entry fast. What structure lets you move an entry to the front and drop the last one fast?
- Hint 2A doubly linked list lets a node remove itself in O(1) because it knows both neighbours.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Your wardrobe has a single rail of shirts. Every time you wear a shirt it goes to the front of the rail. When the rail is full and you buy a new shirt, you give away the shirt at the very back (the one you wore longest ago). A small index card says where each shirt hangs, so you can pull any shirt out instantly without searching the rail.
- The obvious way
Keep a list ordered by recency and search/move items in it: O(n) per operation.
- The key insight
Keep entries in a doubly linked list ordered from most to least recently used, plus a dictionary from key to its node. get: find the node by key, move it to the front, return the value. put: if the key exists update it and move it to the front; otherwise add a new node at the front and, if over capacity, delete the node at the back (and its dictionary entry). Two sentinel nodes at the ends remove edge cases.
- The algorithm
- Make the dictionary and a list with a dummy front and a dummy back.
- get(key): not there -> -1. Otherwise move its node to the front and return the value.
- put(key, value): if it exists, update and move to the front. Else create a node at the front.
- If the cache is now over capacity, remove the node just before the dummy back and delete its key.
Watch it run
Examplecapacity 2: put(1,1) put(2,2) get(1) put(3,3) get(2)
put 1 and put 2: the rail holds [2, 1], newest at the front.
front -> 2, 1 <- back
Where people slip
- Store the key inside each node so that when you evict the last node you know which dictionary entry to delete.
- In Python, collections.OrderedDict does the same job in a few lines, but interviews usually want the manual version.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class Node:
def __init__(self, key=0, value=0):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.nodes = {} # key -> node
self.front, self.back = Node(), Node() # dummy ends of the rail
self.front.next, self.back.prev = self.back, self.front
def _unhook(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _add_front(self, node):
node.prev, node.next = self.front, self.front.next
self.front.next.prev = node
self.front.next = node
def get(self, key):
if key not in self.nodes:
return -1
node = self.nodes[key]
self._unhook(node)
self._add_front(node) # just used: move to the front
return node.value
def put(self, key, value):
if key in self.nodes:
self._unhook(self.nodes[key])
node = self.nodes[key] = Node(key, value)
self._add_front(node)
if len(self.nodes) > self.capacity:
oldest = self.back.prev # the shirt at the very back
self._unhook(oldest)
del self.nodes[oldest.key]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.