Least Recently Used Cache With O(1) Calls
Problem statement
Build a cache that holds at most capacity keys, each with a value, and evicts the least recently used key when it runs out of room. It starts empty and supports two calls:
get(key): ifkeyis in the cache, return its value and mark it as the most recently used key. Otherwise return-1and change nothing.put(key, value): ifkeyis already in the cache, replace its value and mark it as the most recently used. Otherwise, if the cache is full, first remove the least recently used key; then addkeyas the most recently used.
Updating a key that is already in the cache never removes anything.
You get the calls in order as three arrays: operations[i] is "get" or "put", keys[i] is its key and values[i] its value. Return the results of the get calls, in order. Try to make each call take O(1) time.
Function
runLruCache(capacity: int, operations: String[], keys: int[], values: int[]) → int[]Examples
Example 1
capacity = 2operations = ["put","put","get","put","get","get","put","get"]keys = [5,7,5,9,7,9,5,5]values = [50,70,0,90,0,0,55,0]return = [50,-1,90,55]After get 5, key 5 is the most recently used and key 7 the least. So put 9 on a full cache evicts 7, and get 7 returns -1. get 9 returns 90. put 5 55 updates the value of key 5 without evicting anything, so the last get 5 returns 55.
Example 2
capacity = 1operations = ["put","put","get","get"]keys = [1,2,1,2]values = [10,20,0,0]return = [-1,20]With room for one key, put 2 evicts key 1. So get 1 returns -1 and get 2 returns 20.
Example 3
capacity = 3operations = ["get","put","get"]keys = [4,4,4]values = [0,40,0]return = [-1,40]The cache starts empty, so the first get 4 returns -1. After put 4 40, it returns 40.
Constraints
1 <= capacity <= 10001 <= operations.length <= 2000, andkeysandvalueshave the same length asoperations.- Each
operations[i]is"get"or"put", and at least one is"get". 0 <= keys[i] <= 10^4and0 <= values[i] <= 10^5; for a"get",values[i]is0and is ignored.