Design and implement an LRU cache

Problem Statement

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

• get(key): Return the value of the key if it exists in the cache, otherwise return -1. Accessing a key makes it the most recently used.
• put(key, value): Update or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

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

Implementation Signature

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

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

    def put(self, key: int, value: int) -> None:
        # Update value or insert new key-value pair
        pass

Example

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 MRU)
lru.put(3, 3) # Evicts key 2. Cache: {1:1, 3:3}
lru.get(2)    # Returns -1 (not found)

Constraints

• capacity will be between 1 and 1000.
• key and value are non-negative integers.
• Ensure the solution handles empty cache states and eviction correctly.