Design and implement a data structure for Least Recently Used(LRU) cache.
Problem Note:
- The LRU Cache is initialized with a positive capacity
-
Your data structure must support two operations:
get()
andput()
-
get(key)
: finds and returns the value if the key exists in the cache -
If the key is not present in the cache,
get(key)
returns-1
-
put(key, value)
: inserts new key if it is not present in the cache. If the cache is filled to capacity, it must remove the least recently used entry -
Try implementing both operations in
O(1)
time complexity -
Input in this problem would be a series of function calls to
get()
andput()
Example
cache = LRUCache(3)
cache.put(1,1)
cache.put(2,2)
cache.put(1,3)
cache.get(1) ---> returns 3
cache.put(3,4)
cache.put(4,3) // removes key 2
cache.get(2) ---> returns -1
Input Format:
-
First-line contains
N
andC
, the total number of queries and the cache size. -
Each of the following
N
lines has a query of either type 1(put) or type 2(get). -
The query of type 1 is of format:
1 k v
, wherek
is key andv
is value -
Query of type 2 is of format:
2 k
, wherek
is key whose value is to be fetched.
For example, the input for the above example will be:
7 3
1 1 1
1 2 2
1 1 3
2 1
1 3 4
1 4 3
2 2