Least Frequently Used Cache
Problem
Build a cache that holds at most capacity keys. A get returns the key's value, or -1 if it is missing, and counts as a use; a put inserts a key with one use, or updates an existing key's value and counts as a use. When a new key arrives while the cache is full, first evict the key with the fewest uses, and among those the one whose last use is oldest. Given the capacity and a list of operations, return the results of the get calls, with every operation in O(1) average time.
Examples
Input: capacity = 2
ops = put(5, 50), put(6, 60), get(6), get(6), put(7, 70),
get(5), put(5, 55), get(7), get(5)
Output: [60, 60, -1, -1, 55]
Why: 7 evicts 5 (one use against three); later 5 evicts 7 for the same reasonInput: capacity = 2
ops = put(1, 100), put(2, 200), put(1, 111), get(2), put(3, 300),
get(1), get(3)
Output: [200, -1, 300]
Why: 1 and 2 both have two uses, and 1 was used longer ago, so 1 goesInput: capacity = 0
ops = put(1, 1), get(1)
Output: [-1]
Why: edge case, a cache with no room keeps nothingHints
0 / 3
Scanning every key to find the victim is correct but linear per eviction. Think about grouping keys so the victim is always at a known place.
Group keys by their use count. Inside one group, keep keys in the order they were last used, and remember which count is currently the smallest.
Keep key to value, key to count, and count to an insertion-ordered set of keys. A use moves the key from its count's group to the end of the next group; if it emptied the smallest group, the smallest count goes up by one. A brand-new key always resets the smallest count to 1, and eviction pops the oldest key of the smallest group.
Solution
Keys are grouped by use count, and each group is an ordered dictionary with the least recently used key first. The victim is therefore always the first key of the lowest group, and the lowest count only changes in two ways: a use can empty the lowest group, which raises it by exactly one, and a new key sets it back to 1. Every operation touches a constant number of dictionary entries. Time is O(1) average per operation, and space is O(capacity).
from collections import OrderedDict, defaultdict
def run_cache(capacity, ops):
value, uses, groups = {}, {}, defaultdict(OrderedDict) # groups: count -> keys, oldest first
lowest, out = 0, []
def touch(k):
nonlocal lowest
c = uses[k]
del groups[c][k]
if not groups[c]:
del groups[c]
if lowest == c: lowest = c + 1
uses[k] = c + 1
groups[c + 1][k] = None # newest in its new group
for op in ops:
if op[0] == "get":
if op[1] in value: touch(op[1])
out.append(value.get(op[1], -1))
elif capacity:
k, v = op[1], op[2]
if k in value:
value[k] = v; touch(k); continue
if len(value) == capacity:
victim, _ = groups[lowest].popitem(last=False) # fewest uses, oldest
if not groups[lowest]: del groups[lowest]
del value[victim], uses[victim]
value[k], uses[k], lowest = v, 1, 1
groups[1][k] = None
return out
first = [("put", 5, 50), ("put", 6, 60), ("get", 6), ("get", 6), ("put", 7, 70),
("get", 5), ("put", 5, 55), ("get", 7), ("get", 5)]
second = [("put", 1, 100), ("put", 2, 200), ("put", 1, 111), ("get", 2),
("put", 3, 300), ("get", 1), ("get", 3)]
print(run_cache(2, first)) # -> [60, 60, -1, -1, 55]
print(run_cache(2, second)) # -> [200, -1, 300]
print(run_cache(0, [("put", 1, 1), ("get", 1)])) # -> [-1]Stuck on the idea rather than the code? LFU: Frequency Buckets covers it.