Design cache with least-recently-used eviction

You are asked to design an in-memory key–value cache that supports a **least-recently-used (LRU) eviction policy**. The cache must support the following operations: - `get(key) -> value`: - If `key` exists in the cache, return its associated `value` and mark this entry as **most recently used**. - If `key` does not exist, return `-1` (or an equivalent sentinel value indicating a miss). - `put(key, value) -> void`: - Insert or update the value associated with `key`. - If the `key` already exists, update its value and mark it as **most recently used**. - If inserting the new key would cause the number of items in the cache to exceed a fixed **capacity** (given when the cache is created), you must **evict the least recently used** entry first. **Requirements:** - The cache is initialized with an integer `capacity > 0`. - Both `get` and `put` operations must run in **amortized O(1) time**. - Clearly describe the data structures you will use to achieve O(1) time for both operations. **Example behavior (for illustration only):** ```text Initialize cache with capacity = 2 put(1, 1) # cache = {1=1} put(2, 2) # cache = {1=1, 2=2} (2 is most recently used) get(1) -> 1 # returns 1, cache order: 2 (LRU), 1 (MRU) put(3, 3) # capacity exceeded, evict 2 (LRU), cache = {1=1, 3=3} get(2) -> -1 # 2 was evicted put(4, 4) # capacity exceeded, evict 1 (LRU), cache = {3=3, 4=4} get(1) -> -1 # 1 was evicted get(3) -> 3 # returns 3 get(4) -> 4 # returns 4 ```