Meta LRU Cache Operations
Meta● MediumFULLTIMEONSITE INTERVIEWProblem statement
Process an operation sequence on a least-recently-used (LRU) cache with the given capacity. Each operation is an integer array. [1, key, value] means put: insert or replace that key and mark it most recently used. [0, key] means get: return its value if present and mark it most recently used; otherwise return -1 without changing recency.
When inserting a new key would exceed capacity, first evict the least recently used existing key. Replacing an existing key never evicts another key. When capacity is zero, puts store nothing and every get returns -1. Only gets produce outputs. Return their results in operation order.
Recency is ordered by successful gets and puts: the most recently touched key is newest. An unsuccessful get does not touch anything.
Function
runLruCache(capacity: int, operations: int[][]) → int[]Examples
Example 1
capacity = 2operations = [[1,1,10],[1,2,20],[0,1],[1,3,30],[0,2],[0,1],[0,3]]return = [10,-1,10,30]Getting key 1 makes it newest, so inserting key 3 evicts key 2. The later gets return the remaining values.
Example 2
capacity = 2operations = [[1,1,10],[1,2,20],[1,1,15],[1,3,30],[0,2],[0,1]]return = [-1,15]Updating key 1 marks it newest without evicting. Inserting key 3 evicts key 2, and key 1 retains its replacement value.
Example 3
capacity = 0operations = [[1,7,70],[0,7],[1,8,80],[0,8]]return = [-1,-1]A zero-capacity cache never retains a put value.
Example 4
capacity = 1operations = [[1,4,40],[0,9],[1,5,50],[0,4],[0,5]]return = [-1,-1,50]The miss for key 9 does not affect recency. Inserting key 5 evicts the only stored key.
Constraints
0 <= capacity <= 10000.1 <= operations.length <= 10000.- Every operation is exactly
[0, key]or[1, key, value]. 0 <= key, value <= 10^9.