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() 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 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() and put()


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 and C , 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 , 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