Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get and put operations in O(1) time complexity.
1 <= capacity <= 3000, 0 <= key <= 10^4, 0 <= value <= 10^5, At most 2 * 10^5 calls will be made to get and put
Use hash map for O(1) lookup + doubly linked list for O(1) insertion/deletion at both ends. Move accessed items to front, evict from back.
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.order = collections.OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.order.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.order.move_to_end(key)
self.cache[key] = value
self.order[key] = None
if len(self.cache) > self.capacity:
oldest = next(iter(self.order))
del self.cache[oldest]
del self.order[oldest]