Cum proiectezi o cache LRU cu O(1) pentru get și put?

Question

Accepted Answer

Un **cache LRU (Least Recently Used)** elimină elementul care nu a fost accesat timp de cel mai lung interval atunci când atinge capacitatea. Designul clasic combină o **hartă hash** (O(1) căutare) cu o **listă dublu înlănțuită** (O(1) reordonare), oferind **O(1) get și put**. ## Designul cu două structuri ```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) ``` ## Cod ```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` este în sine o hartă hash plus o listă dublu înlănțuită, exact structura descrisă mai sus. | Operație | Timp | |---|---| | get | O(1) | | put | O(1) | | spațiu | O(capacity) | ## De ce lista dublu înlănțuită O listă dublu înlănțuită te lasă să **detașezi un nod din mijloc în O(1)** (ții referință la `prev`/`next` ale sale), ceea ce este imposibil cu o listă simplu înlănțuită sau un array fără a deplasa O(n) elemente. ## De ce contează Cachurile LRU stau în fața bazelor de date, serverelor web și CPU-urilor pentru a păstra datele accesate frecvent rapide și memoria limitată. Această problemă este un clasic la interviuri senior pentru că testează combinarea a două structuri astfel încât *slăbiciunea uneia să fie acoperită de cealaltă* — o abilitate cheie în proiectarea sistemelor.