Design an LRU Cache

Problem: Design an LRU Cache Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity): Initialize the cache with a positive integer capacity. get(key): Return the value of the key if it exists in the cache; otherwise return -1. put(key, value): Update the value of the key if it exists; otherwise insert the key-value pair. If the number of keys exceeds capacity, evict the least recently used key. Requirements: Average time complexity of both get and put must be O(1). Typical Constraints 1 <= capacity <= 1e5 0 <= key, value <= 1e5 Total calls to get/put <= 2e5 Example Input: LRUCache(2) put(1, 1) put(2, 2) get(1) put(3, 3) get(2) put(4, 4) get(1) get(3) get(4) Output: 1 -1 -1 3 4 Example Input LRUCache(2) put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4 Output 1 -1 -1 3 4