Implement an LRU cache

Design and implement an in-memory cache that evicts entries using the **Least Recently Used (LRU)** policy. The cache should store key–value pairs and support the following operations: - `LRUCache(int capacity)`: Initialize the cache with a positive integer `capacity` representing the maximum number of key–value pairs it can hold. - `int get(int key)`: - If the key exists in the cache, return its value and mark this key as **most recently used**. - If the key does not exist, return `-1`. - `void put(int key, int value)`: - Insert or update the value of the given key. - When inserting a new key causes the number of items to exceed `capacity`, you must **evict exactly one key–value pair: the one that has been least recently used** (i.e., the one whose `get` or `put` was accessed furthest in the past). - Updating an existing key should also mark it as **most recently used**. **Requirements:** - All `get` and `put` operations must run in **O(1)** average time. - You may assume: - Keys and values are integers. - `capacity >= 1`. Describe the data structures you would use and then implement the LRU cache in a language of your choice.