Implement an LRU cache

Problem Statement

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support the following operations:

• get(key): Return the value of the key if it exists, otherwise return -1. Accessing a key marks it as the most recently used.
• put(key, value): Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

The get and put operations must run in O(1) average time complexity.

Interface

class LRUCache:
    def __init__(self, capacity: int):
        # Initialize the cache with a positive size capacity
        pass

    def get(self, key: int) -> int:
        pass

    def put(self, key: int, value: int) -> None:
        pass

Example

# Capacity = 2
lru = LRUCache(2)
lru.put(1, 1)    # Cache: {1=1}
lru.put(2, 2)    # Cache: {1=1, 2=2}
lru.get(1)       # Returns 1, Cache: {2=2, 1=1} (1 is now most recent)
lru.put(3, 3)    # Evicts key 2, Cache: {1=1, 3=3}
lru.get(2)       # Returns -1 (not found)

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5

Edge Cases

• Accessing a key that doesn't exist.
• Inserting into a cache that is at full capacity.
• Calling put with an existing key to update its value.