Implement an LRU cache

## LRU Cache Design and implement a fixed-capacity **Least Recently Used (LRU)** cache. ### Operations - `get(key) -> value | -1/null`: Return the value if present; otherwise indicate missing. Accessing a key makes it **most recently used**. - `put(key, value)`: Insert or update the value. Updating also makes it **most recently used**. ### Eviction rule - When inserting causes the cache to exceed capacity, evict the **least recently used** item. ### Requirements - Target time complexity: `O(1)` average for both `get` and `put`. ### Input/Output format You may choose an interface/class-based implementation (common in interviews). Clearly define how missing keys are represented (e.g., `-1` for integers).