LRU Cache
Problem statement
Implement a least recently used (LRU) cache with the given positive capacity, starting empty. Process operations in order.
For this exercise, each row is [kind,key,value]. Kind 0 puts a key/value pair and returns 0. A put replaces an existing value and makes that key most recently used. If a new key would exceed capacity, evict the least recently used live key. Kind 1 gets a key: return its value and make it most recently used when present, or return -1 without changing recency when absent. Value is ignored for get.
Return one answer per operation. Insertion, replacement and successful get all count as use. The operation-array interface and bounds are practice conventions.
Function
runLRU(capacity: int, operations: int[][]) → int[]Examples
Example 1
capacity = 2operations = [[0,1,10],[0,2,20],[1,1,0],[0,3,30],[1,2,0],[1,3,0]]return = [0,0,10,0,-1,30]After two puts the recency order is [1,2]. Getting 1 changes it to [2,1]. Putting 3 evicts 2, so its get misses while key 3 returns 30.
Example 2
capacity = 1operations = [[0,0,0],[0,0,7],[1,0,99],[0,1,8],[1,0,0],[1,1,0]]return = [0,0,7,0,-1,8]Replacing key 0 changes its value to 7 without adding a second entry. Capacity one means putting key 1 evicts 0. Get ignores its third operand.
Constraints
1 <= capacity <= 1000 <= operations.length <= 1000operations[i].length == 30 <= operations[i][j] <= 1000000- Operation kinds are 0 or 1, and keys are at most 10000.