Simulate a Least Recently Used Cache

LRU Cache Implementation

Design and implement a data structure for a Least Recently Used (LRU) cache. The cache must support two main operations: get(key) and put(key, value).

Requirements

• get(key): Return the value of the key if the key 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 exceeds its capacity, evict the least recently used item before adding the new one.
• Both operations must run in O(1) average time complexity.

Class Interface

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

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

    def put(self, key: int, value: int) -> None:
        # Add or update value; evict if capacity is exceeded
        pass

Examples

cache = LRUCache(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)

Edge Cases

• Accessing a key that does not exist.
• Updating a key that already exists.
• Calling put when the cache is at full capacity.
• A capacity of 1.