Implement an LRU Cache

Problem: Implement an LRU Cache Design and implement an LRUCache that follows the Least Recently Used (LRU) eviction policy. It must support: get(key): return the value if the key exists; otherwise return -1. put(key, value): insert or update the key. If the cache reaches capacity, evict the least recently used key first. Requirements Constructor: LRUCache(capacity) where capacity >= 1. Average time complexity of both get and put must be O(1). Constraints Number of operations: 1 <= operations <= 2 * 10^5 0 <= key, value <= 10^9 I/O Format (for this test) Input: Line 1: integer capacity Line 2: integer q number of operations Next q lines: get key put key value Output: Print one line per get operation. Test Cases Case 1 Input: 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output: 1 -1 -1 3 Case 2 Input: 1 6 put 1 10 get 1 put 2 20 get 1 get 2 get 3 Output: 10 -1 20 -1 Case 3 Input: 2 7 put 1 1 put 1 2 get 1 put 2 2 put 3 3 get 2 get 3 Output: 2 -1 3 Case 4 Input: 3 6 get 1 put 1 1 get 1 put 2 2 put 3 3 get 2 Output: -1 1 2 Case 5 Input: 2 5 put 1 1 put 2 2 put 3 3 get 3 get 1 Output: 3 -1 Example Input 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output 1 -1 -1 3