LRU Cache Design

Design and implement a data structure for LRU (Least Recently Used) cache. Implement the operations get and put with O(1) average time complexity. 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 reaches its capacity, it should invalidate the least recently used item before inserting a new item. Constraints: The number of calls to get and put is at most 10^5. Example: LRUCache cache = new LRUCache(2); // Capacity cache.put(1, 1); cache.put(2, 2); cache.get(1); // Returns 1 cache.put(3, 3); // Evicts key 2 cache.get(2); // Returns -1 (not found) cache.put(4, 4); // Evicts key 1 cache.get(1); // Returns -1 (not found) cache.get(3); // Returns 3 cache.get(4); // Returns 4 Example Input 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4