LRU Cache :
Difficulty Level : Medium
Submissions : 27
Asked In :
Marks :10
: 1 | : 0
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Initially, the size of the cache is given. After that, there can be two types of operations:
- get k -> Output the value of the key k if exists, else output -1.
- put k v -> Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Every operation must be done in O(1) time.
Input
The first line contains 2 space separated integers, size (1 <= size <= 1000) and Q (1 <= Q <= 1e5) - size of the cache and number of operations
Next Q lines contains the descriptions of the operation, either of type "put k v" or "get k". (1 <= k <= 1000) (1 <= v <= 1000)
There will be at least one get per test case.
Output
For every get operation encountered, print its answer.
Example
Input
2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Output
1 -1 -1 3 4
