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(key): finds and returns the value if the key exists in the cache
- If the key is not present in the cache,
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
- Input in this problem would be a series of function calls to
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
C, the total number of queries and the cache size.
- Each of the following
Nlines has a query of either type 1(put) or type 2(get).
- The query of type 1 is of format:
1 k v, where
kis key and
- Query of type 2 is of format:
2 k, where
kis 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