A cache that evicts the least frequently used key in O(1): a map from key to node, plus one list per use count and a pointer to the lowest count.
▼The problem
LeetCode 460 (Hard). Implement LFUCache(capacity) with get(key) (the value, or -1 if the key is missing) and put(key, value) (insert or update). When a put of a new key finds the cache full, evict the least frequently used key; on a tie, the least recently used of them. A get or put of an existing key counts as a use. Both calls must run in O(1) average time.
Example (LeetCode's): LFUCache(2), put(1,1), put(2,2), get(1) → 1, put(3,3) evicts 2 (one use against two), get(2) → -1, get(3) → 3, put(4,4) evicts 1 (1 and 3 both have two uses; 1 is older), get(1) → -1, get(3) → 3, get(4) → 4.
The solution
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap, self.min_freq = capacity, 0
self.node = {} # key -> [value, freq]
self.bucket = defaultdict(OrderedDict) # oldest first
def touch(self, key): # one more use
f = self.node[key][1]
del self.bucket[f][key]
if f == self.min_freq and not self.bucket[f]:
self.min_freq += 1
self.node[key][1] = f + 1
self.bucket[f + 1][key] = None
def get(self, key):
if key not in self.node: return -1
self.touch(key)
return self.node[key][0]
def put(self, key, value):
if key in self.node:
self.node[key][0] = value
return self.touch(key)
if len(self.node) == self.cap: # full: evict
old, _ = self.bucket[self.min_freq].popitem(last=False)
del self.node[old]
self.node[key] = [value, 1]
self.bucket[1][key] = None
self.min_freq = 1Transcript
LFU Cache. A cache holds at most capacity keys. Get returns a key's value, or minus one. Put stores a value. When full, evict the least frequently used key; on a tie, the least recently used. Both in constant time.
Capacity two. Put one, put two, get one: one has two uses now. Put three: two has the fewest uses, so two is evicted; get two returns minus one.
The slow way: keep a count per key, and on every eviction, scan every key for the lowest count, then the oldest. That's order n work per put.
The key idea: one bucket per use count, each kept oldest first, plus the minimum count. LRU kept one line; LFU keeps one line per frequency. A use moves a key up one bucket. Evict from the front of the minimum bucket.
In code: a map from key to value and count, an ordered dict per count, and min freq. Touch moves a key up; if that empties the minimum bucket, the minimum rises. A new key starts at one, and so does the minimum.
Back to the example, with buckets. Get three: it moves to bucket two, bucket one empties, so the minimum is two. Put four: one and three tie at two uses; one is older, so it goes. Four starts at one. Then minus one, three, and four.
Each call is a few hash lookups and one move: constant time. Space grows with capacity.
Count every use, bucket by count, evict the oldest of the least used. That's LFU Cache.