Implement an LRU Cache

## Problem Design and implement an **LRU (Least Recently Used) Cache** that supports the following operations in **O(1) average time**: - `get(key)`: - Return the value associated with `key` if it exists in the cache. - Otherwise return `-1`. - This operation marks `key` as **most recently used**. - `put(key, value)`: - Insert or update the `(key, value)` pair. - This operation marks `key` as **most recently used**. - If inserting causes the number of keys to exceed the cache `capacity`, evict the **least recently used** key. ## Requirements - Implement a class (or module) that is initialized with an integer `capacity`. - Both operations should run in **O(1)** average time. ## Notes / Edge Cases - Updating an existing key should overwrite its value and update its recency. - `capacity` is a positive integer. ## Example Given `capacity = 2`: 1. `put(1, 1)` 2. `put(2, 2)` 3. `get(1)` → returns `1` (key `1` becomes most recently used) 4. `put(3, 3)` → evicts key `2` 5. `get(2)` → returns `-1` 6. `put(4, 4)` → evicts key `1` 7. `get(1)` → returns `-1` 8. `get(3)` → returns `3` 9. `get(4)` → returns `4`