Implement an LRU cache

## Problem Design and implement an **LRU (Least Recently Used) cache** that supports the following operations in **average O(1)** time: - `get(key) -> value`: Return the value associated with `key` if it exists in the cache; otherwise return `-1`. Accessing a key makes it **most recently used**. - `put(key, value)`: Insert or update the value for `key`. If inserting causes the number of keys to exceed the cache `capacity`, evict the **least recently used** key. ## Input/Output You will implement a class (or module) with: - Constructor: `LRUCache(capacity)` - Methods: `get(key)` and `put(key, value)` ## Constraints (typical) - `1 <= capacity <= 10^5` - Keys and values are integers (or comparable scalar types) - Must achieve **O(1)** average time for both operations and **O(capacity)** space ## Notes - “Most recently used” means most recently accessed via `get` or updated via `put`. - Updating an existing key counts as a recent use.