Implement an LRU Cache

Problem Statement

Design and implement a data structure for a Least Recently Used (LRU) cache. The cache should support get(key) and put(key, value) operations with O(1) average time complexity.

Requirements

• get(key): Returns the value of the key if the key exists in the cache, otherwise returns -1. Accessing a key marks it as the most recently used.
• put(key, value): Updates the value of the key if the key exists. Otherwise, adds 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.

Interface

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

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

    def put(self, key: int, value: int) -> None:
        # Inserts or updates the value
        pass

Example

cache = LRUCache(2) # capacity = 2
cache.put(1, 1)     # cache is {1: 1}
cache.put(2, 2)     # cache is {1: 1, 2: 2}
cache.get(1)        # returns 1, cache is {2: 2, 1: 1}
cache.put(3, 3)     # evicts key 2, cache is {1: 1, 3: 3}
cache.get(2)        # returns -1 (not found)

Constraints

• capacity will be between 1 and 100,000.
• key and value are integers.
• Operations can reach up to 200,000 calls.