Come progetti una cache LRU con get e put O(1)?

Question

Accepted Answer

Una **cache LRU (Least Recently Used)** rimuove l'elemento che non è stato accessato per il tempo più lungo quando raggiunge la capacità. Il design classico combina una **hash map** (lookup O(1)) con una **doubly linked list** (riordinamento O(1)), ottenendo **get e put O(1)**. ## Il design a due strutture ```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) ``` ## Code ```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` è esso stesso una hash map più una doubly linked list, esattamente la struttura descritta sopra. | Operazione | Tempo | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Perché la doubly linked list Una doubly linked list ti permette di **staccare un nodo dal mezzo in O(1)** (tieni i suoi `prev`/`next`), cosa impossibile con una singly linked list o array senza uno shift O(n). ## Perché è importante Le cache LRU stanno davanti a database, web server e CPU per mantenere i dati hot veloci e la memoria limitata. Questo problema è un classico dei colloqui senior perché testa la combinazione di due strutture in modo che *la debolezza di ognuna sia coperta dall'altra* — una skill chiave nel system design.