Jak navrhnete LRU cache s O(1) get a put?

Question

Accepted Answer

**LRU (Least Recently Used) cache** vyprazdňuje položku, ke které se po nejdelší dobu nepřistupovalo, když dosáhne kapacity. Klasický design kombinuje **hash mapu** (O(1) vyhledávání) s **doubly linked list** (O(1) přeuspořádání), což dává **O(1) get a put**. ## Dvoustrukturní design ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Kód ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) 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 least recently used ``` `OrderedDict` je sám o sobě hash mapa plus doubly linked list, přesně struktura popsaná výše. | Operace | Čas | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Proč doubly linked list Doubly linked list vám umožňuje **odpojit uzel ze středu v O(1)** (máte jeho `prev`/`next`), což je u singly linked list nebo pole bez O(n) posunu nemožné. ## Proč to záleží LRU cache se nacházejí před databázemi, webovými servery a CPU, aby zachovaly hot data rychlá a paměť omezená. Tento problém je typickou otázkou senior interview, protože testuje kombinování dvou struktur tak, aby *každá pokryla slabou stránku druhé* - klíčová dovednost v design systémů.