from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)Variables
c- capacity of the cache
Explanation
Both `get` and `put` use only O(1) hash and pointer operations - **O(1)** per operation. The cache holds at most `c` entries (the capacity), giving **O(c)** space overall. The trick: a hashmap alone is not enough - you also need ordering, which is what makes the doubly-linked-list pairing necessary in a hand-rolled implementation.