Jak zaprojektujesz cache LRU z O(1) dla operacji get i put?

Question

Accepted Answer

**Cache LRU (Least Recently Used)** usuwa element, który nie był dostępny przez najdłuższy czas, gdy osiągnie limit pojemności. Klasyczne projektowanie łączy **hash mapę** (O(1) wyszukiwanie) z **dwukierunkową listą wiązaną** (O(1) zmiana kolejności), dając **O(1) dla get i put**. ## Projektowanie dwóch struktur ```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) ``` ## Kod ```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` jest sam w sobie hash mapą plus dwukierunkową listą wiązaną, dokładnie strukturą opisaną powyżej. | Operacja | Czas | |---|---| | get | O(1) | | put | O(1) | | pamięć | O(capacity) | ## Dlaczego dwukierunkowa lista wiązana Dwukierunkowa lista wiązana pozwala **odłączyć węzeł ze środka w O(1)** (trzymasz jego `prev`/`next`), co jest niemożliwe z listą jednokierunkową lub tablicą bez przesunięcia O(n). ## Dlaczego to ważne Cache'e LRU znajdują się przed bazami danych, serwerami webowymi i procesorami, aby utrzymać gorące dane szybkie i pamięć ograniczoną. Ten problem jest standardem rozmów kwalifikacyjnych dla seniorów, ponieważ testuje łączenie dwóch struktur tak, aby *słabości jednej były pokryte przez drugą* — kluczowa umiejętność w projektowaniu systemów.