Leetcode 146. LRU Cache
📅2023-07-18🧐100
https://leetcode.com/problems/lru-cache/
Let's think about the Least Recently Used (LRU) cache, to run get() and put() in O(1) time complexity, we must have sequence in our solution. What kind of data structure has sequence?
The answer is Linked-list, And move the node or item in a linked-list just using O(1) time.
In this question, we could use Doubly linked-list, it has ability bidirectionally access it looks like this:
Since the removal just need to change the next and previous pointer, so we could fast remove an item.
Another data structure will be used in our solution is hashmap, so we could fast query if our node is existing.
In the solution we need to build the Node object(class) first, then add logic of doubly linked-list directly to make our code concise. And don't forget head and tail just special nodes, but they still are Node.
class Node:
def __init__(self, key=None, val=None):
self.prev = None
self.next = None
self.key = key
self.val = val
class LRUCache:
def __init__(self, capacity: int):
self.cache = {} # to save key and node, so we could access the node by O(1)
self.size = 0
self.capacity = capacity
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _delete_node(self, node):
_prev = node.prev
_next = node.next
_prev.next = _next
_next.prev = _prev
def _add_to_head(self, node):
_next = self.head.next
_prev = _next.prev
node.next = _next
node.prev = _prev
_next.prev = node
self.head.next = node
def _move_to_head(self, node):
self._delete_node(node)
self._add_to_head(node)
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self._move_to_head(self.cache[key])
return self.cache[key].val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key].val = value
self._move_to_head(self.cache[key])
return self.cache[key].val
if self.size >= self.capacity:
tailkey = self.tail.prev.key
self._delete_node(self.tail.prev)
del self.cache[tailkey]
self.size -= 1
node = Node(key, value)
self._add_to_head(node)
self.cache[key] = node
self.size += 1If we use Java, we could implement with builtin LinkedHashMap
class LRUCache {
int capacity;
LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new LinkedHashMap<>(1, 0.75f, true){
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> node){
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}In Python we also have builtin OrderedDict to make life easier
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key, True)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key, True)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(False)In the end let's take a look on the source code of Python's OrderedDict in this link:
LRU cache also can be used to cache overlapping subproblems, so we could use it to solve top-down dynamic programming (DP) problems.
Once we are very familiar with LRU, we can move forward to LFU problem:
https://leetcode.com/problems/lfu-cache/
And please check my solution here if you like:
https://freeyeti.net/leetcode-460-lfu-cache/
LRU is a very useful data structure, for example, when you swipe up on your iPhone screen, you will find LRU. Also the frontend of my blog built by Nextjs, which used LRU to cache server side rendering data.