DesignHash MapLinked List
Design a cache with a fixed capacity that evicts the least recently used item when it is full. get key returns the value (or -1 if absent) and marks the key as most recently used. put key value stores the pair (updating an existing key) and also marks it as most recently used; if the cache then exceeds its capacity, the least recently used key is removed. Both operations should run in O(1) time. You are given a list of operations.
Input
Line 1: the capacity and q, the number of operations. Next q lines: put k v or get k.
Output
For every get print the value, or -1, one per line.
Constraints
1 <= capacity <= 3000 1 <= q <= 10^4 1 <= k <= 10^4, 1 <= v <= 10^9
Example 1
Input
2 6 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3
Output
1 -1 3
Adding 3 evicts key 2, because key 1 was used more recently.