Leetcode 460. LFU Cache
📅2023-07-18🧐77
Don't afraid about the hard label on this problem. If you could understand LRU cache (https://freeyeti.net/leetcode-146-lru-cache/) this question would be easy.
Simplely, after reading the description we could know LFU cache is just LRU cache with a counter, so in this problem our focus is to design a data structure that can save counter along the LRU. Intuitively, we know hashmap could get value in a O(1) time complexity, so we just use it.
let's take a look on my draft for this problem. And usually this is how I start to think about a question, just use the text editor or IDE directly:
0 "LFUCache" [2] null
1 "put" [1,1] null
2 "put" [2,2] null
3 "get" [1] 1
4 "put" [3,3] null
5 "get" [2] -1
6 "get" [3] 3
7 "put" [4,4] null
8 "get" [1] -1
9 "get" [3] 3
10 "get" [4] 4
step1:
freq[1] = {1:1}
counter[1] = 1 # counter[key] saves how many times this key has been used, the value of counter[key] is the key of freq, so we can faster navigate to that OrderedDict
step2:
freq[1] = {1:1, 2:2}
counter[1] = 1
counter[2] = 1
step3:
freq[1] = {2:2}
freq[2] = {1:1}
counter[1] = 2
counter[2] = 1
step4:
freq[1] = {3:3} # we pop 2 since it's the least recent one
freq[2] = {1:1}
counter[1] = 2
counter[2] = 0
counter[3] = 1
step 6:
freq[1] = {}
freq[2] = {1:1, 3:3}
# since OrderedDict always add new item to the most right, don't worry the order
counter[1] = 2
counter[2] = 0
counter[3] = 2
step 7:
freq[1] = {4:4}
freq[2] = {3:3} # we pop 1
counter[1] = 0
counter[2] = 0
counter[3] = 2
counter[4] = 1Let me try to draw the idea:
See, the solution is pretty simple, just use LRU cache with a hashmap to save the count of useage like here:
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity: int):
self.cache = {}
self.counter = defaultdict(int)
self.freq = defaultdict(OrderedDict)
self.min = 0
self.cap = capacity
def update(self, key):
count = self.counter[key]
self.counter[key] += 1
if key in self.freq[count]:
self.freq[count].move_to_end(key)
self.freq[count].popitem()
self.freq[count + 1][key] = key
if count == self.min and len(self.freq[count]) == 0:
self.min = count + 1
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.update(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if self.cap == 0:
return
if key not in self.cache and self.cap == len(self.cache):
res, _ = self.freq[self.min].popitem(False)
del self.cache[res]
self.counter[res] = 0
self.cache[key] = value
self.update(key)
self.min = min(self.min, self.counter[key])
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)