Kako zasnuješ LRU cache z O(1) get in put?

Question

Accepted Answer

**LRU (Least Recently Used) cache** izloči element, ki se ga ni dostopalo najdlje časa, ko doseže kapaciteto. Klasični dizajn kombinira **hash map** (O(1) lookup) z **dvovezno povezano listo** (O(1) preureditev), kar daje **O(1) get in put**. ## Dizajn z dvema strukturama ```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) ``` ## Koda ```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 sam po sebi hash map plus dvovezna povezana lista, natanko struktura, ki je opisana zgoraj. | Operacija | Čas | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Zakaj dvovezna povezana lista Dvovezna povezana lista ti omogoča, da **odstraniš vozlišče iz sredine v O(1)** (držiš `prev`/`next`), kar je nemogoče s singlino povezano listo ali poljem brez O(n) premika. ## Zakaj je to pomembno LRU cachaji se nahajajo pred bazami podatkov, spletnimi strežniki in procesorji, da ohranijo vroče podatke hitre in pomnilnik omejen. Ta problem je osnovna naloga za senior interview, ker preverja kombiniranje dveh struktur tako, da *vsaka druga pokriva slabosti* — ključna veščina zasnove sistema.