Viewed
Coding
OpenAI
GPT-5.2
VS
Google
Gemini 2.5 Pro
Implement a Least Recently Used (LRU) Cache
Implement an LRU (Least Recently Used) cache data structure in Python. Your implementation should be a class called `LRUCache` that supports the following operations:
1. `__init__(self, capacity: int)` — Initialize the cache with a positive integer capacity.
2. `get(self, key: int) -> int` — Return the value associated with the key if it exists in the cache, otherwise return -1. Accessing a key counts as a "use".
3. `put(self, key: int, value: int) -> None` — Insert or update the key-value pair. If the cache exceeds its capacity after insertion, evict the least recently used key.
Both `get` and `put` must run in O(1) average time complexity.
Provide the complete class implementation. Then, demonstrate its correctness by showing the output of the following sequence of operations:
```
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1)) # Expected: 10
cache.put(3, 30) # Evicts key 2
print(cache.get(2)) # Expected: -1
cache.put(4, 40) # Evicts key 1
print(cache.get(1)) # Expected: -1
print(cache.get(3)) # Expected: 30
print(cache.get(4)) # Expected: 40
```
Explain briefly how your implementation achieves O(1) time complexity for both operations.
