Design LRU Cache

What You'll Build

• The cache must support get(key) operation that returns the value associated with the key if it exists, or -1 if the key is not found. This operation must run in O(1) time complexity.
• The cache must support put(key, value) operation that inserts a new key-value pair or updates an existing one. This operation must run in O(1) time complexity.
• When a key is accessed via get() or updated via put(), it should be marked as the most recently used item and moved to the front of the access order.
• When the cache reaches its capacity and a new item needs to be added, the least recently used item (at the tail) must be evicted before adding the new item.
• The cache must maintain a fixed capacity specified during initialization. The capacity must be positive and cannot be changed after initialization.
• ...and more