Comment concevez-vous un cache LRU avec O(1) pour get et put ?

Question

Accepted Answer

Un **cache LRU (Least Recently Used)** évince l'élément qui n'a pas été accédé depuis le plus longtemps lorsqu'il atteint sa capacité. La conception classique combine une **table de hachage** (O(1) lookup) avec une **liste doublement chaînée** (O(1) réorganisation), donnant **O(1) get et put**. ## The two-structure 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) ``` ## 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` est lui-même une table de hachage plus une liste doublement chaînée, exactement la structure décrite ci-dessus. | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Why the doubly linked list Une liste doublement chaînée vous permet de **détacher un nœud du milieu en O(1)** (vous maintenez ses `prev`/`next`), ce qui est impossible avec une liste chaînée simple ou un array sans un décalage O(n). ## Pourquoi c'est important Les caches LRU se situent devant les bases de données, les serveurs web et les CPU pour maintenir les données chaudes rapidement et délimiter la mémoire. Ce problème est un incontournable des entretiens séniors car il teste la combinaison de deux structures de sorte que *la faiblesse de chacune soit couverte par l'autre* — une compétence clé en conception de systèmes.