LFU Cache
Problem statement
Design a cache class LFUCache with a fixed capacity and two operations:
get(key)returns the value stored forkey, or-1if the key isn't cached.put(key, value)stores or updates the value forkey. If this adds a new key and the cache is already full, first evict one key: the one used the fewest times. If several keys tie on that count, evict the one used least recently among them.
A key's use count starts at 1 when it is inserted and goes up by one on every get or put that touches it. A key that is evicted and later re-inserted starts again at 1. With capacity 0, nothing is ever stored. Both operations should run in O(1) average time.
Examples
Example 1
Input: capacity = 2: put(7,70), put(8,80), get(7), get(7), get(8), put(9,90), get(8), get(9)
Output: [70, 70, 80, -1, 90]
Explanation: Before 9 arrives, key 7 has been used 3 times and key 8 twice, so 8 is evicted. The list shows the results of the get calls in order.
Example 2
Input: capacity = 2: put(4,40), put(5,50), put(6,60), get(4), get(5)
Output: [-1, 50]
Explanation: Keys 4 and 5 both have count 1 when 6 arrives. The tie goes to recency, and 4 is older, so 4 is evicted.
Hints
Approach
Frequency buckets with recency order. Keep:
values[key]andcounts[key];buckets[count], an insertion-ordered set of keys with that count, oldest first;min_freq, the smallest count that currently has keys.
To touch a key (on get, or put of an existing key): remove it from buckets[count], and if that bucket is now empty and count == min_freq, increase min_freq. Then increment the count and append the key to the new bucket, where it is the most recent.
To insert a new key when full: evict the oldest key in buckets[min_freq], the first item. Then add the new key with count 1 to buckets[1] and set min_freq = 1.
Every step is a hash lookup or an ordered-set insert or removal at a known position, so both operations are O(1) on average. Python's OrderedDict and Java's LinkedHashSet provide the ordered sets.
O(1) per operationSpace O(capacity)from collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity): self.capacity = capacity self.values = {} self.counts = {} self.buckets = defaultdict(OrderedDict) # count -> keys, oldest first self.min_freq = 0 def _touch(self, key): count = self.counts[key] del self.buckets[count][key] if not self.buckets[count]: del self.buckets[count] if self.min_freq == count: self.min_freq += 1 self.counts[key] = count + 1 self.buckets[count + 1][key] = None def get(self, key): if key not in self.values: return -1 self._touch(key) return self.values[key] def put(self, key, value): if self.capacity == 0: return if key in self.values: self.values[key] = value self._touch(key) return if len(self.values) == self.capacity: victim, _ = self.buckets[self.min_freq].popitem(last=False) if not self.buckets[self.min_freq]: del self.buckets[self.min_freq] del self.values[victim] del self.counts[victim] self.values[key] = value self.counts[key] = 1 self.buckets[1][key] = None self.min_freq = 1 c = LFUCache(2)c.put(7, 70)c.put(8, 80)out = [c.get(7), c.get(7), c.get(8)]c.put(9, 90)out += [c.get(8), c.get(9)]print(out) c = LFUCache(2)c.put(4, 40)c.put(5, 50)c.put(6, 60)print([c.get(4), c.get(5)])Follow-up questions
- Implement the simpler LRU Cache in O(1) (a hash map plus a doubly linked list, or an
OrderedDict). - Add a time-to-live per key so that expired entries are treated as missing and evicted first.
Frequently asked questions
Cache eviction policy is a real infra decision: CDN edges, database buffer pools, DNS resolvers and in-process caches all choose something to throw away when memory runs out. LFU is the harder sibling of LRU and tests whether you can combine hash maps and ordered structures so every operation stays constant time.
A touch moves one key from count c to c + 1. If that empties the bucket for c and c was the minimum, the key that just moved now sits at c + 1, so the new minimum is exactly c + 1. Inserting a new key always resets the minimum to 1, so no search is ever needed.
LFU remembers old popularity. A key that was hot yesterday keeps a high count and can crowd out keys that are hot now. Production caches often use variants that age or decay counts, or policies such as W-TinyLFU that mix frequency with recency, to avoid that.