Wie designst du einen LRU-Cache mit O(1) get und put?

Question

Accepted Answer

Ein **LRU-Cache (Least Recently Used)** entfernt den Eintrag, auf den über die längste Zeit nicht zugegriffen wurde, wenn die Kapazität erreicht ist. Das klassische Design kombiniert eine **Hash-Map** (O(1) Lookup) mit einer **doppelt verketteten Liste** (O(1) Umordnung) und ergibt **O(1) get und put**. ## Das Zwei-Strukturen-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` ist selbst eine Hash-Map plus eine doppelt verkettete Liste, genau die oben beschriebene Struktur. | Operation | Zeit | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Warum die doppelt verkettete Liste Eine doppelt verkettete Liste ermöglicht dir, einen Knoten aus der Mitte in O(1) zu trennen (du hältst sein `prev`/`next`), was mit einer einfach verketteten Liste oder einem Array ohne O(n) Verschiebung unmöglich ist. ## Warum es wichtig ist LRU-Caches befinden sich vor Datenbanken, Webservern und CPUs, um Hot Data schnell zu halten und den Speicher begrenzt zu halten. Dieses Problem ist eine Standardfrage bei Senior-Interviews, weil es das Kombinieren von zwei Strukturen testet, bei denen *jede die Schwäche der anderen abdeckt* - eine Schlüsselfähigkeit im System-Design.