medium
hashmap
linked-list
design
Implement a key-value cache with a fixed capacity. The cache removes the least recently used key whenever adding a new key would exceed that capacity.
Process the three parallel arrays from left to right. At index i:
put: storevalues[i]underkeys[i]. If the key already exists, replace its value. This key becomes the most recently used.get: look upkeys[i]. Append its value to the result, or append-1if it is absent. A successful lookup makes the key the most recently used.values[i]is ignored for this operation.
Only get operations produce output. Return their results in the order the operations occurred.
When an insertion exceeds capacity, evict the key whose most recent successful get or put happened earliest. Updating an existing key does not increase the number of keys in the cache.
Constraints
1 <= capacity <= 3,0001 <= operations.length <= 10,000operations.length == keys.length == values.length- Every operation is
putorget - Keys and values are integers
Follow-up
Can you make both get and put run in O(1) average time?
Examples
Example 1
Input: capacity = 2, operations = ["put","put","get","put","get","put","get","get","get"], keys = [1,2,1,3,2,4,1,3,4], values = [1,2,0,3,0,4,0,0,0]
Output: [1,-1,-1,3,4]
Example 2
Input: capacity = 1, operations = ["put","get"], keys = [1,1], values = [10,0]
Output: [10]
Example 3
Input: capacity = 1, operations = ["put","put","get","get"], keys = [1,2,1,2], values = [1,2,0,0]
Output: [-1,2]
🔒 5 hidden
Running will execute all 8 cases, including 5 hidden ones.