Design and Implement an LRU Cache

Design and implement a data structure for a Least Recently Used (LRU) cache that supports get and put operations. get(key) - Get the value of the key if the key exists in the cache, otherwise return -1. put(key, value) - Update the value of the key if the key exists, otherwise add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key. The operations must be done in O(1) time complexity. 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