ChiPy Algorithms SIGDescription
Design and implement a data structure for Least Frequently Used (LFU) cache
get(key) Get the value of the key if the key exists in the cache, otherwise return -1
put(key, value) Set or insert the value if the key is not already present. When the cache reaches its capacity, it should delete the least frequently used item before inserting a new item. When there is a tie, delete the least recently used item!
Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted (e.g. the “frequency”). This number is set to zero when the item is removed.
lfu = LFUCache(2) # Capacity is 2
lfu.get(key) # Return value if exists, else return -1
lfu.put(key, value) # Create or update the value. Delete item to make room when needed!
lfu.put(1, 1) # 1 used once
lfu.put(2, 2) # 1 used once, 2 used once
lfu.get(1) # 1 used twice, 2 used once (returns 1)
lfu.put(3, 3) # 1 used twice, 3 used once (2 is removed!)
lfu.get(2) # Returns -1 since 2 is gone!
Solution by beginner789
from collections import defaultdict, deque
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.frequency = defaultdict(deque)
self.minimum = float('inf')
def get(self, key: int) -> int:
if key not in self.cache:
return -1
value, count = self.cache[key]
self.frequency[count].remove(key)
if not self.frequency[count]:
del self.frequency[count]
if count == self.minimum:
self.minimum += 1
self.frequency[count + 1].append(key)
self.cache[key] = value, count + 1
return value
def _evict(self) -> None:
if not self.frequency:
''' edge case
["LFUCache","put","get"]
[[0],[0,0],[0]]
'''
return
remove = self.frequency[self.minimum].popleft()
if not self.frequency[self.minimum]:
del self.frequency[self.minimum]
self.minimum += 1
del self.cache[remove]
def put(self, key: int, value: int) -> None:
if key not in self.cache:
if len(self.cache.keys()) == self.capacity:
self._evict()
if len(self.cache.keys()) < self.capacity:
self.cache[key] = (value, 1)
self.frequency[1].append(key)
self.minimum = 1
else:
_, count = self.cache[key]
self.frequency[count].remove(key)
if not self.frequency[count]:
del self.frequency[count]
if count == self.minimum:
self.minimum += 1
self.cache[key] = (value, count + 1)
self.frequency[count + 1].append(key)