Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.int get(int key) Return the value of the key if the key exists, otherwise return -1.void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.Follow up:
Could you do get and put in O(1) time complexity?
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 10^43 * 10^4 calls will be made to get and put.
The description was taken from https://leetcode.com/problems/lru-cache/.
class Node: def __init__(self, key:int, val:int): self.key, self.val = key, val self.prev = self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = {} self.least, self.most = Node(0,0), Node(0,0) self.size = 0 self.least.next, self.most.prev = self.most, self.least def insert(self, node:Node) -> None: prev_node, next_node = self.most.prev, self.most prev_node.next = next_node.prev = node node.prev, node.next = prev_node, next_node def remove(self, node:Node) -> None: prev_node, next_node = node.prev, node.next prev_node.next, next_node.prev = next_node, prev_node def get(self, key: int) -> int: if key in self.cache: self.remove(self.cache[key]) self.insert(self.cache[key]) return self.cache[key].val else: return -1 def put(self, key: int, value: int) -> None: if key in self.cache: self.remove(self.cache[key]) self.size -= 1 self.cache[key] = Node(key,value) self.insert(self.cache[key]) self.size += 1 if self.size > self.cap: lru = self.least.next self.remove(lru) del self.cache[lru.key] self.size -=1For constant get and put functions, we can use a dictionary to store our cache values.
However, seeing as we need to delete the least recently used value, we will need a list to keep track of what value was the least recently used, based on some kind of order within the list.
Since we are going to be adding and removing values, we will want to use a linked list so that the rest of the list doesn't need to shift each time we add or remove a value. If we were going to use a singly linked list, it may be difficult to add and remove nodes between the head and tail.
To avoid that, we will use also use a doubly-linked list, where each node has a previous and a next value.
Before we start messing with the cache, let's start by building the Node class.
Each node will contain a key that will help for distinguishing it, a value, a prev node pointer, and a next node pointer.
class Node: def __init__(self, key:int, val:int): self.key, self.val = key, val self.prev = self.next = None
Now let's start working on the LRUCache class.
The class will have as attributes, a cap which is the maximum capacity specified, a cache which will be a HashMap or Python dictionary, a least dummy node that will act as the head of the list, a most dummy node that will act as the tail, a size counter that will keep track of how many occupants are in the cache.
class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = {} self.least, self.most = Node(0,0), Node(0,0) self.size = 0
Initially, with an empty list, the least and most dummy nodes will point to each other.
self.least.next, self.most.prev = self.most, self.least
def insert(self, node:Node) -> None:
If we are inserting a node into the list then at the time of insertion, the node is the most recently used node.
To signify this, we will put this node at the far-right end of the list, right before the dummy tail, the most node.
In order to do this, we will first mark what nodes will be the previous and next node of the node we are about to insert, let's say we are about to insert five for example.
The previous node will be the node that is currently the most recently used, and the next node will be the dummy most node.
least<=>1<=>2<=>3<=>4<=>most
prev_node, next_node = self.most.prev, self.most
We will first connect the other nodes' pointers to the insertion node.
least<=>1<=>2<=>3<=>4->5<-most
prev_node.next = next_node.prev = node
Then we will connect the insertion node's pointers to the previous node and the most node.
least<=>1<=>2<=>3<=>4<=>5<=>most
node.prev, node.next = prev_node, next_node
Our remove function will be very similar to the insert.
def remove(self, node:Node) -> None:
Let's say we wanted to remove four. The previous node would be three and the next node would be four.
We will point to those nodes.
least<=>1<=>2<=>3<=>4<=>5<=>most
prev_node, next_node = node.prev, node.next
We will point the previous node to the next node, and the next node to the previous node. This will lose our reference to this node, deleting it from our list.
least<=>1<=>2<=>3<=>5<=>most
prev_node.next, next_node.prev = next_node, prev_node
The get function will be next.
def get(self, key: int) -> int:
We will check if the key of the value is in the cache, this is a constant time operation.
If it is, we will pluck this node from its current place in the list and insert it back by the most node because this node has become the most recently used node at this point in time.
if key in self.cache: self.remove(self.cache[key]) self.insert(self.cache[key])
After we have reordered the node, we will return the node value. Remember, self.cache[key] would return the node itself, but we are wanting to return the actual value of the node, so we will return self.cache[key].val.
return self.cache[key].val
If the key of the value is not in the cache, we will return a negative one as instructed.
else: return -1
Lastly, let's build the put function.
def put(self, key: int, value: int) -> None:
This is the tricky part of the question because if our cache is at maximum capacity, we have to kick out the least recently used value.
When we're putting a new value in the cache, we will first check if it's already there.
If it is, then this is just a matter of updating the key in the cache with a fresh new node.
We'll remove the current node of this key from the list and decrement the cache's size by one. The reason for decrementing the size is because we are going to increment the size for each put call, and we aren't actually increasing the size of the cache by updating the key. This will lead to a net-zero size increase after the function has run.
if key in self.cache: self.remove(self.cache[key]) self.size -= 1
Afterward, we will put the key into our cache, with its value being a node we will instantiate.
We'll insert the node into the list and increment the size of the cache by one.
self.cache[key] = Node(key,value) self.insert(self.cache[key]) self.size += 1
Since we just added a value to the cache, we will need to make sure we aren't over the capacity.
If we are, we will get the least used node from the list which will be right after the dummy least node, we'll remove it from the list and delete it from the cache. We can then decrement the size of the cache by one and get back under capacity.
least<=>1<=>2<=>3<=>5<=>most
least<=>2<=>3<=>5<=>most
if self.size > self.cap: lru = self.least.next self.remove(lru) del self.cache[lru.key] self.size -= 1