LFU cache
Build a class LFUCache that stores up to capacity key-value pairs and, when it runs out of room, forgets the least frequently used (LFU) key: the key with the fewest uses. If several keys share that fewest count, it forgets the least recently used of them, the one whose last use is furthest in the past. A key is used each time a get finds it or a put stores it.
LFUCache(capacity)makes an empty cache.get(key)returns the value stored forkey, or-1if the key is not in the cache. Agetthat finds the key counts as a use.put(key, value)storesvalueunderkey, replacing the old value if the key is already there. It counts as a use. If the key is new and the cache already holdscapacitykeys, first remove the least frequently used key, as above. A new key starts with one use.
A removed key loses its count: if it comes back later, it starts again at one use. Both methods must take O(1) time on average, however many keys the cache holds.
LFUCache(2), put(5, 50), get(5), put(8, 80), put(9, 90), get(5), get(8), get(9)Outputthe four gets return 50, 50, -1, 90Key 5 has two uses and key 8 one, so put(9, 90) removes key 8, though key 8 was used more recently. An LRU cache would have removed key 5.
LFUCache(3), put(1, 10), put(2, 20), put(3, 30), get(3), get(1), get(2), put(4, 40), get(3), get(4)Outputthe five gets return 30, 10, 20, -1, 40Keys 1, 2 and 3 all have two uses. Key 3's last use is the oldest of the three, so put(4, 40) removes it.
LFUCache(2), put(1, 10), put(2, 20), put(1, 11), put(3, 30), get(1), get(2), get(3)Outputget(1) returns 11, get(2) returns -1, get(3) returns 30Updating key 1 counts as a use, so key 1 has two uses and key 2 one: key 2 goes.
1 ≤ capacity ≤ 104
Keys and values are integers, and values are never negative, so -1 always means "missing".
Up to 2 × 105 calls in total.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.