Loading page…
Evict the least frequently used key, least recently used among ties, with frequency buckets and a running minimum so every get and put is O(1).
LRU keeps what was used recently; LFU (least frequently used) keeps what is used often, and evicts the key with the fewest accesses (Week 0, Part 6, section 11.2): with counts A(10), B(2), C(5), D(1), the next insert evicts D. Popular keys survive a burst of one-off reads that would flush an LRU cache. The interview twist is doing it in O(1): a heap of counts is O(log n), and scanning for the minimum is O(n).
Implement LFUCache(capacity):
| Method | Does |
|---|---|
get(key) |
the value, or None on a miss. A hit is a use: the key's count goes up by 1 |
put(key, value) |
an existing key: update the value, and that's a use too (count + 1); never evicts. A new key: if the cache is full, evict first, then insert it with count 1 |
freq(key) |
the key's count (0 if it isn't cached) |
delete(key) |
removes the key; True if it was there |
__len__() |
number of keys |
order() |
every key in eviction order, next victim first: lowest count first, and among equal counts the least recently used first |
Eviction the key with the lowest count; among keys with that count, the one used least recently. A miss changes nothing. capacity below 1 raises ValueError.
O(1) get and put must not scan the keys or sort anything; the scale test runs 100,000 operations and flags anything that grows faster than linear. For the per-count recency lists, use OrderedDict in Python (popitem(last=False) is O(1)) and the given KeyList in JavaScript: the lru-cache lab built that list by hand, and the new idea here is the buckets around it. Don't use a plain dict's or a Map's first key as a queue: both leave deleted slots in place until the table is rebuilt, so after many deletions, finding the first key walks over them and eviction quietly turns O(n). order() is for the tests and can take O(n log n).
In JavaScript and TypeScript: get returns null on a miss, size is a getter in place of __len__, order() returns an array, and a capacity below 1 throws RangeError. KeyList (given) has append(key) (adds at the end, or moves an existing key there), remove(key), popFirst(), has(key), size and keys().
Keep three maps: key → value, key → count, and count → keys with that count, in recency order, plus min_freq, the lowest count in use. A use moves a key from bucket f to the end of bucket f + 1; eviction pops the front of bucket min_freq. This is the scheme published by Shah, Mitra and Matani, "An O(1) algorithm for implementing the LFU cache eviction scheme" (2010).
Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.