Design and implement a data structure for Least Recently Used(LRU) cache.
- The LRU Cache is initialized with a positive capacity
- Your data structure must support two operations: get() and put()
- 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's 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() and put()
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
First line contains N and C, the total number of queries and the cache size.
Each of the following N lines have a query of either type 1(put) or type 2(get).
Query of type 1 is of format: 1 k v, where k is key and v is value
Query of type 2 is of format: 2 k, where k 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