Challenge #1: Implement a LRU Cache

An LRU (Least Recently Used) cache is a type of data structure that stores a limited number of items. When the cache reaches its limit, it removes the least recently used item before inserting a new one.

Your task is to implement an LRU cache class with the following methods:

1. put(key: int, value: int) -> None: Inserts the key-value pair into the cache. If the cache is full, it should evict the least recently used item.

2. get(key: int) -> int: Returns the value of the key if it exists in the cache, otherwise returns -1.

Requirements:

• The cache should have a maximum capacity, specified at initialization.

• All operations (put and get) should be in O(1) time complexity.

Here’s how the interface should look:

cache = LRUCache(2)  # Capacity of 2

cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # Returns 1
cache.put(3, 3)      # Evicts key 2
print(cache.get(2))  # Returns -1 (not found)
cache.put(4, 4)      # Evicts key 1
print(cache.get(1))  # Returns -1 (not found)
print(cache.get(3))  # Returns 3
print(cache.get(4))  # Returns 4