LRU Cache

Design a LRU (Least Recently Used) cache mechanism that supports the following operations: get(key) and put(key, value). get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Example input & output Given a capacity of 2, the sequence of operations: put(1, 1) put(2, 2) get(1) returns 1 put(3, 3), LRU key is 2 and gets evicted get(2) returns -1 (not found) put(4, 4), LRU key is 1 and gets evicted get(1) returns -1 (not found) get(3) returns 3 get(4) returns 4 Constraints 1 <= capacity <= 3000 0 <= key, value <= 10^4 The number of calls to put and get is up to 10^5. Example Input 7 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4