Implement an LRU cache

## Problem: LRU Cache Design and implement a data structure that supports an **LRU (Least Recently Used) cache** with a fixed capacity. ### Requirements Implement a cache with the following operations: - `get(key) -> value` - If `key` exists in the cache, return its value and mark the entry as **most recently used**. - If `key` does not exist, return `-1`. - `put(key, value) -> void` - Insert or update the `(key, value)` pair. - If inserting causes the number of keys to exceed `capacity`, evict the **least recently used** entry. - Updating an existing key should also mark it as **most recently used**. ### Performance Constraints - Target time complexity: **O(1)** average for both `get` and `put`. - Space complexity: **O(capacity)**. ### Example Assume `capacity = 2`: - `put(1, 10)` - `put(2, 20)` - `get(1) -> 10` (now key `1` is most recently used) - `put(3, 30)` (evicts key `2` as least recently used) - `get(2) -> -1` ### Notes You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.