Least Frequently Used Cache Simulator
Problem statement
A cache holds at most capacity keys, each with a value. It starts empty. Every key also has a use count.
get(key): if the key is in the cache, return its value and add 1 to its use count. Otherwise return-1and change nothing.put(key, value): if the key is already in the cache, set its new value and add 1 to its use count; nothing is removed. If the key is new and the cache is full, first remove one key: the one with the smallest use count. If several keys share that smallest count, remove the one whose last get or put happened longest ago. Then add the new key with use count 1.
The calls come as three arrays: call i is operations[i] on key keys[i], and values[i] is the value for a "put" (it is 0 for a "get"). Return the results of the "get" calls, in order.
Function
runLfuCache(capacity: int, operations: String[], keys: int[], values: int[]) → int[]Examples
Example 1
capacity = 2operations = ["put","put","get","get","put","get","get","get"]keys = [3,8,3,3,6,8,3,6]values = [30,80,0,0,60,0,0,0]return = [30,30,-1,30,60]Key 3 is used three times (one put, two gets) and key 8 once. When key 6 arrives the cache is full, so the least used key, 8, is removed: get 8 returns -1, while keys 3 and 6 return 30 and 60.
Example 2
capacity = 2operations = ["put","put","put","get","get","get"]keys = [1,2,3,1,2,3]values = [10,20,30,0,0,0]return = [-1,20,30]Keys 1 and 2 are both used once. That is a tie, so the one used longer ago, key 1, is removed when key 3 arrives.
Example 3
capacity = 1operations = ["put","put","get"]keys = [4,4,4]values = [40,44,0]return = [44]Putting key 4 again only updates its value; nothing is removed, and get 4 returns 44.
Constraints
1 <= capacity <= 10001 <= operations.length <= 2000, andkeys.length == values.length == operations.length- Each
operations[i]is"get"or"put", and at least one is"get". 0 <= keys[i] <= 10^40 <= values[i] <= 10^5, andvalues[i] == 0whenoperations[i]is"get".