Hvordan utformer du en LRU-cache med O(1) get og put?

Question

Accepted Answer

En **LRU (Least Recently Used) cache** fjerner elementet som ikke har blitt tilgjengd på lengst tid når den når kapasiteten. Det klassiske designet kombinerer en **hash map** (O(1) oppslag) med en **dobbeltlenket liste** (O(1) omordning), noe som gir **O(1) get og put**. ## Designet med to strukturer ```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) ``` ## Kode ```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` er selv en hash map pluss en dobbeltlenket liste, nøyaktig strukturen beskrevet ovenfor. | Operasjon | Tid | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Hvorfor dobbeltlenket liste En dobbeltlenket liste lar deg **detaljere en node fra midten i O(1)** (du holder `prev`/`next`), noe som er umulig med en enkeltlenket liste eller array uten en O(n) skift. ## Hvorfor det betyr noe LRU-cacher sitter foran databaser, webservere og CPUer for å holde hot data rask og minne begrenset. Dette problemet er et klassisk senior-intervju fordi det tester kombinering av to strukturer slik at *hver andres svakhet dekkes* — en nøkkel system-design-ferdighet.