LRU Cache Implementation from Scratch
An LRU (Least Recently Used) cache achieves $O(1)$ gets, $O(1)$ puts, and $O(1)$ evictions by pairing a hash map (fast lookup) with an `OrderedDict` or doubly linked list (fast recency reordering) ⚡.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache: return -1
self.cache.move_to_end(key) # Mark as recently used ⚡
return self.cache[key]
def put(self, key: int, value: int):
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) # Evict oldest! 🗑️
lru = LRUCache(2)
lru.put(1, 10); lru.put(2, 20)
print(lru.get(1)) # 10 (key 1 is now newest)
lru.put(3, 30) # Evicts key 2!
print(lru.get(2)) # -1 (Not found) ❌
# 13. LRU Cache Implementation from Scratch An LRU (Least Recently Used) cache achieves $O(1)$ gets, $O(1)$ puts, and $O(1)$ evictions by pairing a hash map (fast lookup) with an `OrderedDict` or doubly linked list (fast recency reordering) ⚡. ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) # Mark as recently used ⚡ return self.cache[key] def put(self, key: int, value: int): 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) # Evict oldest! 🗑️ lru = LRUCache(2) lru.put(1, 10); lru.put(2, 20) print(lru.get(1)) # 10 (key 1 is now newest) lru.put(3, 30) # Evicts key 2! print(lru.get(2)) # -1 (Not found) ❌ ``` This is the exact underlying algorithmic architecture that powers `@functools.lru_cache`, Redis caches, and CPU hardware cache lines! ⚡ --- ### Question Why does a standard Python dictionary need an eviction strategy like LRU when caching unbounded web requests? 🧠 - [ ] a. Without eviction, an unbounded cache grows indefinitely until the system runs out of RAM (OOM) 🛑 - [ ] b. Standard dictionaries automatically delete keys after 60 seconds - [ ] c. Dictionaries can only store up to 256 items in Python - [ ] d. It causes an immediate syntax error at runtime --- ### Challenge Create an `LRUCache(capacity=2)` using `OrderedDict`. Put `(1, 100)`, `(2, 200)`. Read key `1`. Put `(3, 300)`. Print `cache.get(2)`. 🎯 <details> <summary>Solution</summary> ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int): 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) lru = LRUCache(2) lru.put(1, 100) lru.put(2, 200) lru.get(1) lru.put(3, 300) print(lru.get(2)) ``` </details>