LFU Cache

Hard · design

A cache remembers at most capacity key and value pairs. It starts empty and receives a list of operations. operations[i] is either "get" or "put", and args[i] holds its arguments: [key] for a "get" and [key, value] for a "put".

"get" returns the value stored for key, or -1 if the key is not in the cache.
"put" stores value for key. If the key is already in the cache its value is replaced. If it is a new key and the cache already holds capacity pairs, first remove one pair, as described below.

Every pair has a use count. A new pair starts at 1. Each "get" that finds the key, and each "put" that replaces the value of an existing key, adds 1 to that pair's count. A "get" for a missing key changes nothing.

When a pair must be removed, remove the one with the smallest use count. If several pairs share the smallest count, remove the one that was used least recently (read, written or added the longest time ago). A removed pair forgets its count: if its key is added again later it starts from 1.

Return a list with the result of every "get", in the order they appear.

Examples

Example 1

Input: capacity = 2, operations = ["put", "put", "get", "get", "put", "get", "get", "put", "get", "get"], args = [[5, 50], [6, 60], [5], [5], [7, 70], [6], [7], [8, 80], [5], [7]]

Output: [50, 50, -1, 70, 50, -1]

When key 7 arrives, key 5 has been used 3 times and key 6 only once, so key 6 is removed. When key 8 arrives, key 5 has count 3 and key 7 has count 2, so key 7 is removed.

Example 2

Input: capacity = 2, operations = ["put", "put", "get", "get", "put", "get", "get", "get"], args = [[1, 10], [2, 20], [1], [2], [3, 30], [1], [2], [3]]

Output: [10, 20, -1, 20, 30]

Keys 1 and 2 both have count 2 when key 3 arrives. Key 1 was used less recently, so it is removed.

Example 3

Input: capacity = 1, operations = ["put", "put", "put", "get", "get"], args = [[4, 40], [4, 41], [9, 90], [4], [9]]

Output: [-1, 90]

With room for one pair, adding key 9 removes key 4 whatever its count.

Constraints

1 <= capacity <= 1000
1 <= len(operations) <= 10^4
len(args) == len(operations)
operations[i] is get or put
0 <= key <= 10^5
0 <= value <= 10^9