Build an LRU Cache with a Hash Map and Linked List

LRU Cache Design

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

• get(key): Return the value of the key if the key exists, otherwise return -1.
• 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.

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

Requirements

• Class LRUCache with __init__(self, capacity: int)
• get(key: int) -> int
• put(key: int, value: int) -> None

Example

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)
lru.put(4, 4)    # evicts key 1, cache is {3=3, 4=4}
lru.get(1)       # returns -1 (not found)
lru.get(3)       # returns 3
lru.get(4)       # returns 4

Constraints

• Capacity is a positive integer.
• Keys and values are integers.
• Ensure the cache handles updating an existing key's value correctly by treating it as a "use" (making it the most recent).