A phone app keeps a small cache of saved items, so it does not have to fetch them again. The cache can hold only a few pairs. When it is full and a new key arrives, it must throw one old pair away.
This cache throws away the key that was used the fewest times. It is called a Least Frequently Used (LFU) cache.
Write a class LFUCache with these methods:
LFUCache(capacity): make an empty cache that holds at most capacity pairs.get(key): return the value saved for key, or -1 if key is not in the cache.put(key, value): save the pair. If key is already there, replace its value. If key is new and the cache is full, first throw away the key with the fewest uses.
If several keys have the same fewest uses, throw away the one that was used longest ago.
Each key has a use count. A new key starts at 1, because its put is a use. Every later get or put of that key adds 1.
Both get and put must run in O(1) average time.
Examples
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get"]
[[2], [10, 100], [20, 200], [10], [30, 300], [20], [30], [40, 400], [10]]
Output
[null, null, null, 100, null, -1, 300, null, -1]
Explanation
The cache holds at most 2 pairs. After put(10, 100) and put(20, 200), get(10) returns 100. Key 10 now has 2 uses and key 20 has 1.
put(30, 300) needs room, so key 20 (fewest uses) is thrown away. get(20) returns -1 and get(30) returns 300.
Keys 10 and 30 both have 2 uses. put(40, 400) throws away key 10, because it was used longer ago. So get(10) returns -1.
Example 2:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "get"]
[[2], [1, 11], [2, 22], [1], [3, 33], [2], [3], [1]]
Output
[null, null, null, 11, null, -1, 33, 11]
Explanation
get(1) returns 11, so key 1 has 2 uses and key 2 has 1 use.
put(3, 33) throws away key 2, which has the fewest uses.
get(2) returns -1. get(3) returns 33. get(1) returns 11.