Implement an LRU Cache

Design and implement a fixed-capacity key-value cache that evicts the least recently used item when it becomes full. Support the following operations: - `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. - `put(key, value)`: Insert or update the value for `key`. If inserting a new key causes the cache to exceed its capacity, remove the least recently used entry. A key becomes most recently used whenever it is accessed by `get` or updated/inserted by `put`. Requirements: - The cache capacity is given in the constructor. - Both `get` and `put` should run in average `O(1)` time. - You may choose any reasonable class or function interface.