Implement an LRU Cache

Problem: Implement an LRU Cache Design and implement a cache with a Least Recently Used (LRU) eviction policy. You must support two operations: get(key): Return the value for key if it exists in the cache; otherwise return -1. put(key, value): Insert or update the (key, value) pair. If inserting causes the cache to exceed its fixed capacity, evict the least recently used entry. Requirements Both get and put should run in O(1) (amortized) time. The cache has a fixed capacity. Constraints (reference) 1 <= capacity <= 1e5 1 <= operations <= 2e5 key and value are 32-bit integers Example Input (operation sequence): capacity = 2 put(1, 1) put(2, 2) get(1) -> 1 put(3, 3) (evict key=2) get(2) -> -1 put(4, 4) (evict key=1) get(1) -> -1 get(3) -> 3 get(4) -> 4 Output: 1, -1, -1, 3, 4 Example Input capacity=2; ops=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