LFU Cache

Build a key-value cache with a fixed number of slots. When it is full and a new key arrives, it throws out the key that has been used the fewest times (the least frequently used key).

Write the class LFUCache:

• LFUCache(capacity) creates an empty cache that holds at most capacity keys.
• get(key) returns the value stored for key, or -1 if key is not in the cache.
• put(key, value) stores value under key, replacing the old value if key is already there. If key is new and the cache already holds capacity keys, first remove one key by the rule below, then add key.

Every key in the cache has a use count:

• A put that adds a key sets its count to 1.
• A get that finds a key, and a put that updates a key, each add 1 to its count.
• A get that returns -1 changes nothing.

Which key is removed: the key with the smallest use count. If several keys share that smallest count, remove the one among them whose most recent use (its latest get or put) came earliest. A removed key is forgotten completely: if it is added again later, its count starts again at 1.

Both get and put must take O(1) time on average.

Each example lists the calls in order, then each call's arguments, then each call's result (null for the constructor and for put).

Example 1

Input:
["LFUCache", "put", "put", "get", "get", "put", "get", "get", "get"]
[[2], [4, 40], [6, 60], [4], [4], [8, 80], [6], [4], [8]]
Output: [null, null, null, 40, 40, null, -1, 40, 80]

Before put(8, 80), key 4 has count 3 and key 6 has count 1, so 6 is removed, even though 4 was not the most recently added.

Example 2

Input:
["LFUCache", "put", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 5], [2, 7], [2], [1], [3, 9], [2], [1], [3]]
Output: [null, null, null, 7, 5, null, -1, 5, 9]

Keys 1 and 2 both reach count 2. Key 2 was last used before key 1 was, so the tie removes 2.

Example 3

Input:
["LFUCache", "put", "put", "put", "put", "get", "get"]
[[2], [3, 1], [5, 2], [3, 4], [7, 6], [5], [3]]
Output: [null, null, null, null, null, -1, 4]

Updating key 3 raises its count to 2, so when 7 arrives, key 5 (count 1) is removed.

Constraints

• 1 <= capacity <= 10⁴
• 0 <= key <= 10⁵
• 0 <= value <= 10⁹
• At most 2 * 10⁵ calls in total are made to get and put.