Problem · Design
LRU Cache Variation
Learn this problem● Medium
SquarespaceINTERNONSITE INTERVIEW
SquarespaceINTERNONSITE INTERVIEWProblem statement
Implement a least recently used (LRU) cache by processing an ordered batch of operations. The cache has a fixed positive capacity and starts empty.
The parallel arrays operations and arguments describe each call:
gethas arguments[key]. Append the stored value to the answer, or append-1when the key is absent. A successful read makes the key most recently used.puthas arguments[key, value]. Insert or update the key and make it most recently used. Before a new insertion that would exceed capacity, evict the least recently used key.
Return the values produced by get calls in their original order. Updates do not produce output.
Function
processLruVariation(capacity: int, operations: String[], arguments: int[][]) → int[]Examples
Example 1
capacity = 2operations = ["put","put","get","put","get","put","put","get","get","get"]arguments = [[1,10],[2,20],[1],[3,30],[2],[1,15],[4,40],[3],[1],[4]]return = [10,-1,-1,15,40]The read of key 1 causes key 2 to be evicted next. Updating key 1 refreshes it, so inserting key 4 then evicts key 3.
Example 2
capacity = 1operations = ["get","put","get","put","get","get"]arguments = [[7],[7,0],[7],[8,8],[7],[8]]return = [-1,0,-1,8]The first read misses. Value 0 is stored normally. With capacity 1, inserting key 8 evicts key 7.
Constraints
1 <= capacity <= 10^51 <= operations.length <= 2 * 10^5operations.length == arguments.length- Each operation is exactly
getorput. - A
getrow contains exactly one integer, and aputrow contains exactly two integers. 0 <= key <= 10^90 <= value <= 10^9