Design a Recency-Eviction Cache

Problem Statement

Design and implement a data structure for a Least Recently Used (LRU) cache. The cache should have a fixed capacity n and support the following operations:

1. get(key): Returns the value of the key if it exists in the cache, otherwise return -1. If the key is accessed, it must be marked as the most recently used item.
2. put(key, value): Updates the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the cache reaches its capacity before adding the new item, it must remove the least recently used item.

Your implementation must ensure that both get and put operations run in average O(1) time complexity.

Interface

class LRUCache:
    def __init__(self, capacity: int):
        # Initialize cache with fixed capacity
        pass

    def get(self, key: int) -> int:
        # Return value or -1
        pass

    def put(self, key: int, value: int) -> None:
        # Add or update key-value pair
        pass

Examples

Example 1:

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
       [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

• put(1, 1), put(2, 2): Cache is {1: 1, 2: 2}.
• get(1): Returns 1, cache becomes {2: 2, 1: 1} (1 is now most recent).
• put(3, 3): Cache full, evicts 2. Cache is {1: 1, 3: 3}.
• get(2): Returns -1 (not found).
• put(4, 4): Cache full, evicts 1. Cache is {3: 3, 4: 4}.

Constraints

• capacity will be between 1 and 100,000.
• key and value will be non-negative integers.
• Total operations will not exceed 200,000.