Design an LRUCache class: a key value cache with a fixed capacity that evicts the least recently used key when it is full. LRUCache(capacity) creates it, get(key) returns the value or -1 if the key is missing, and put(key, value) inserts or updates the key. Reading or writing a key makes it the most recently used. If a put adds a new key beyond capacity, remove the least recently used key first. Both get and put must run in O(1) average time.
get(1) makes key 1 recent, so put(3,3) evicts key 2. Then put(4,4) evicts key 1.- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls to get and put
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A naive version stores keys with a "last used" timestamp and scans for the smallest timestamp when evicting: O(capacity) per eviction. To make everything O(1), we need two things at once: find a key instantly (hash map) and keep keys ordered by recency with O(1) moves (doubly linked list). The map stores key to list node. The list keeps the most recent node right after a head sentinel and the least recent node just before a tail sentinel. Because the list is doubly linked, a node can unlink itself in O(1) once the map hands it to us.
Algorithm
- Keep a map from key to node and a doubly linked list with
headandtailsentinel nodes. get: if the key is missing return -1; otherwise move its node to the front and return its value.puton an existing key: update the value and move the node to the front.puton a new key: create a node, add it at the front and to the map.- If the size now exceeds capacity, remove the node before
tailfrom the list and its key from the map.
O(1) per get and putSpace: O(capacity)LinkedHashMap or OrderedDict, so practise the hand-written list.class DNode: 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: int): self.capacity = capacity self.map = {} # key -> DNode self.head = DNode() # most recent side self.tail = DNode() # least recent side self.head.next = self.tail self.tail.prev = self.head def _unlink(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: int) -> int: node = self.map.get(key) if node is None: return -1 self._unlink(node) self._add_front(node) # now the most recent return node.val def put(self, key: int, value: int) -> None: node = self.map.get(key) if node: node.val = value self._unlink(node) self._add_front(node) return node = DNode(key, value) self.map[key] = node self._add_front(node) if len(self.map) > self.capacity: lru = self.tail.prev # least recently used self._unlink(lru) del self.map[lru.key]