Design a LRU Cache

Design a data structure that can perform the following operations in constant time O(1): add key-value pairs, retrieve the value of a specific key. Specifically, implement a class LRUCache: LRUCache(int capacity): Initialize the LRU cache with positive integer capacity. int get(int key): Returns the value of the key if present in the cache (always a positive integer), otherwise return -1. void put(int key, int value): If the key is already present in the cache, update its value; otherwise, insert the new key-value pair. When the cache reaches its capacity, it should evict the least recently used key. Ensure that all operations are O(1) time complexity. Example: # Initialize the cache capacity as 2 lru_cache = LRUCache(2) assert lru_cache.get(1) == -1 # returns -1 (not found) lru_cache.put(1, 1); # cache is {1=1} lru_cache.put(2, 2); # cache is {1=1, 2=2} assert lru_cache.get(1) == 1 # returns 1 lru_cache.put(3, 3); # evicts key 2, cache is {1=1, 3=3} assert lru_cache.get(2) == -1 # returns -1 (not found) lru_cache.put(4, 4); # evicts key 1, cache is {3=3, 4=4} assert lru_cache.get(1) == -1 # returns -1 (not found) assert lru_cache.get(3) == 3 # returns 3 assert lru_cache.get(4) == 4 # returns 4 Example Input capacity = 2, operations = [("put", 1, 1), ("put", 2, 2), ("get", 1), ("put", 3, 3), ("get", 2), ("put", 4, 4), ("get", 1), ("get", 3), ("get", 4)]