Process Get and Set Operations in a Key-Value Cache

LRU Cache Implementation

Design and implement a data structure for an LRU (Least Recently Used) cache. The cache should support get(key) and put(key, value) operations with the following requirements:

• get(key): Returns the value of the key if it exists, otherwise returns -1.
• put(key, value): Updates the value of the key if it 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.

Implement the class LRUCache:

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

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

    def put(self, key: int, value: int) -> None:
        # Update the value of the key if it exists, otherwise add the pair
        pass

Constraints

• 1 <= capacity <= 100,000
• 0 <= key <= 1,000,000
• 0 <= value <= 1,000,000,000
• Operations should run in O(1) average time complexity.

Examples

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