O(1) get ve put ile bir LRU cache'yi nasıl tasarlarsınız?

Question

Accepted Answer

**LRU (Least Recently Used) cache**, kapasiteye ulaştığında en uzun süredir erişilmemiş öğeyi çıkarır. Klasik tasarım, **hash map** (O(1) lookup) ile **çift yönlü bağlı liste** (O(1) yeniden sıralama) birleştirerek **O(1) get ve put** sağlar. ## İki yapılı tasarım ```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` kendisi bir hash map artı çift yönlü bağlı liste olup, yukarıda açıklanan yapıyla tamamen aynıdır. | İşlem | Zaman | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Çift yönlü bağlı liste neden Çift yönlü bağlı liste, bir düğümü ortadan **O(1) içinde ayırmanıza** izin verir (`prev`/`next` tutuyorsunuz), bu da tek yönlü bağlı liste veya O(n) kayması olmadan dizi ile imkansızdır. ## Neden önemli LRU cache'ler, veritabanları, web sunucuları ve CPU'lar önünde oturarak sıcak veriler hızlı ve bellek sınırlı kalır. Bu problem, senior düzey mülakat için temel bir sorundur çünkü iki yapının birleştirilmesini test eder, öyle ki *her birinin diğerinin zayıflığını kapatması* — anahtar sistem tasarımı becerisidir.