Python'da get ve put işlemleri O(1) olan bir LRU cache sınıfı yazın.

LRU (Least Recently Used) cache, kapasite dolduğunda en uzun süredir kullanılmayan öğeyi atar. O(1) için hash map + çift yönlü bağlı liste gerekir; Python'da OrderedDict ikisini birlikte sunar.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.data: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)          # en son kullanılan yap
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # en eskiyi at

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
cache.get(1)       # 1  -> sıra: 2, 1
cache.put(3, 3)    # 2 atılır
cache.get(2)       # -1

Mülakatçı OrderedDict'e izin vermezse

Kendi dict[key -> Node] yapınızı ve head/tail sentinel'li çift yönlü bağlı listenizi yazarsınız: get'te node'u listeden çıkarıp başa eklersiniz, put'ta kapasite aşılırsa tail'in önündeki node'u silip dict'ten de çıkarırsınız. Her işlem birkaç pointer değişikliğidir, yani O(1).

Gerçek hayatta

• Fonksiyon sonuçları için standart kütüphane: functools.lru_cache(maxsize=1024) veya functools.cache.
• Bu cache process içidir: birden fazla worker ya da pod arasında paylaşılmaz. Paylaşılan cache için Redis kullanılır.
• Thread'ler arasında paylaşılacaksa threading.Lock ile korunmalıdır.