LRU cache

Problem

Sabit kapasiteli bir LRU (least recently used) cache sınıfı yaz:

• LRUCache(capacity): pozitif kapasiteyle oluşturur.
• get(key): anahtar varsa değerini döndürür, yoksa -1.
• put(key, value): anahtarı ekler ya da değerini günceller. Ekleme kapasiteyi aşacaksa önce en uzun süredir kullanılmayan anahtar atılır.

Hem get hem put bir anahtarı "kullanılmış" yapar. İki işlem de ortalama O(1) olmalı.

cache = LRUCache(2)
put(1, 10); put(2, 20)
get(1)       -> 10      sıra (eskiden yeniye): 2, 1
put(3, 30)   -> 2 atılır (en eski)
get(2)       -> -1
put(1, 11)   -> güncelleme de kullanım: sıra 3, 1
put(4, 40)   -> 3 atılır
get(3)       -> -1
get(1)       -> 11

Netleştirme soruları

• Var olan bir anahtarı put ile güncellemek kullanım sayılır mı? (Evet.)
• Kapasite 0 ya da negatif gelebilir mi? (LeetCode'da hayır; production'da constructor'da reddetmek doğru.)
• Anahtar/değer tipleri? (Burada int; genel bir cache <K, V> olurdu ve "yok" için -1 yerine Optional dönerdi.)
• Thread-safe olmalı mı? (Takip sorusunun ana konusu.)

İpuçları

Yaklaşım

Kaba çözüm: Her girdiye bir zaman damgası koy; tahliyede tüm girdileri tarayıp en eskiyi bul. get O(1) ama tahliye O(n). Ya da LinkedList'te remove(Object) ile taşıma: O(n).

HashMap + çift yönlü liste (seçilen çözüm): Map anahtardan liste düğümüne gider; liste kullanım sırasını tutar.

• get: map'ten düğümü bul, listeden çıkar (O(1), çünkü düğüm prev ve next'i biliyor), başa ekle.
• put (var olan): değeri güncelle, başa taşı.
• put (yeni): kapasite doluysa tail.prev en eskidir; listeden ve map'ten (node'daki key ile) sil. Yeni düğümü başa ekle ve map'e koy.

Sentinel head ve tail düğümleri sayesinde gerçek düğümlerin her zaman bir prev ve next'i vardır; null kontrolü gerekmez.

Java'nın hazır cevabı: LinkedHashMap. LinkedHashMap zaten bir hash tablosu ile girdileri birbirine bağlayan çift yönlü bir listenin birleşimidir. accessOrder = true ile her get/put girdiyi listenin sonuna taşır; removeEldestEntry her eklemeden sonra çağrılır ve true dönerse en eski girdi silinir:

import java.util.LinkedHashMap;
import java.util.Map;

public final class LinkedHashMapLruCache {

    private final Map<Integer, Integer> map;

    public LinkedHashMapLruCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.map = new LinkedHashMap<>(16, 0.75f, true) {        // accessOrder = true: get de sırayı günceller
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;                        // put'tan sonra çağrılır
            }
        };
    }

    public int get(int key) { return map.getOrDefault(key, -1); }

    public void put(int key, int value) { map.put(key, value); }
}

Mülakatta doğru sıra: önce "Java'da bunu LinkedHashMap ile birkaç satırda yazarım" demek ve yazmak; mülakatçı "kendi veri yapını yaz" derse manuel versiyona geçmek. Sadece LinkedHashMap yazıp duran aday, mekanizmayı bilip bilmediğini göstermemiş olur. Tuzak: accessOrder parametresi verilmezse varsayılan ekleme sırasıdır; sonuç LRU değil FIFO olur.

Java çözümü

import java.util.HashMap;
import java.util.Map;

public final class LRUCache {

    private static final class Node {
        final int key;                                    // tahliye sırasında map'ten silmek için gerekli
        int value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> index = new HashMap<>();
    private final Node head = new Node(0, 0);             // sentinel: en yeni tarafı
    private final Node tail = new Node(0, 0);             // sentinel: en eski tarafı

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = index.get(key);
        if (node == null) return -1;
        moveToFront(node);                                // okuma da "kullanım" sayılır
        return node.value;
    }

    public void put(int key, int value) {
        Node node = index.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }
        if (index.size() == capacity) {
            Node eldest = tail.prev;
            unlink(eldest);
            index.remove(eldest.key);
        }
        Node created = new Node(key, value);
        linkFirst(created);
        index.put(key, created);
    }

    private void moveToFront(Node node) {
        unlink(node);
        linkFirst(node);
    }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void linkFirst(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Karmaşıklık

• Zaman: get ve put ortalama O(1) (HashMap ortalama O(1), liste işlemleri O(1)).
• Bellek: O(capacity); her girdi için bir map girdisi ve bir düğüm (iki işaretçi + anahtar + değer).

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Yukarıdaki senaryo: get kullanımı sırayı değiştiriyor, en eski atılıyor, güncelleme kullanım sayılıyor.
• Kapasite 1: her yeni anahtar öncekini atıyor; aynı anahtarın güncellenmesi tahliyeye yol açmıyor. Bu test >=/> off-by-one hatasını hemen yakalar.
• Kapasite 0: IllegalArgumentException.
• LinkedHashMap versiyonunda getOrDefault'un da erişim sırasını güncellediği doğrulandı.
• 50 tur × 2.000 rastgele işlem (kapasite 1-5, anahtar 0-7): manuel versiyon ile LinkedHashMap versiyonu her get'te aynı sonucu verdi.

Mülakatçı için

LRU, backend mülakatlarının en sık sorulan tasarım sorularındandır. Gözlemle: iki yapıyı neden birleştirdiğini açıklıyor mu? Node'da key tutmanın gerekçesini biliyor mu? Sentinel kullanıyor mu ya da null kontrollerini doğru yapıyor mu? put ile güncellemede sırayı güncelliyor mu?

Thread-safety takip sorusu (asıl ayırt edici kısım): "Bu cache'i birden fazla thread kullanacak" de ve dinle:

• HashMap ve bağlı liste thread-safe değildir; eşzamanlı put'lar listeyi bozabilir (kopuk ya da döngülü işaretçiler).
• En basit doğru çözüm: get ve put'u synchronized yapmak (ya da Collections.synchronizedMap(new LinkedHashMap<>(..., true))). Doğru, ama tüm cache tek kilide bağlanır.
• Tuzak: ReadWriteLock ile get'i okuma kilidine almak yanlıştır; LRU'da get listeyi değiştirir, yani bir yazma işlemidir. accessOrder = true olan LinkedHashMap'te de get yapısal değişikliktir.
• ConcurrentHashMap + ConcurrentLinkedDeque birleşimi tek tek thread-safe yapılar olsa da "map'ten bul, listede taşı" bileşik işlemi atomik değildir.
• Ölçeklenebilir yaklaşımlar: kilit bölme (anahtar hash'ine göre N bağımsız LRU segmenti; global değil yaklaşık LRU), okumaları bir buffer'a kaydedip sırayı toplu güncellemek. Production cevabı Caffeine'dir: Window TinyLFU politikası ve okuma/yazma buffer'larıyla yüksek eşzamanlılık, TTL, istatistik.

İpucu zamanlaması: 5 dakikada iki yapıyı birleştirme fikri gelmezse ilk ipucunu ver. Manuel listeyi yazarken işaretçi hatalarında takılırsa sentinel ipucunu ver. Kodlama 20 dakikayı geçerse thread-safety tartışmasına mutlaka zaman ayır; senior sinyali oradan gelir.

Takip sorusu 1: Thread-safe yap ve yüksek eşzamanlılıkta ölçeklendir. Beklenen: yukarıdaki maddeler; önce synchronized, sonra segmentli kilit ya da Caffeine; LRU'nun kesinliğinden ne kadar ödün verildiğini söylemek.

Takip sorusu 2: Her girdiye TTL ekle. Beklenen: düğümde expiresAt; get'te süresi dolmuşsa sil ve -1 dön (lazy expiration); kapasiteyi işgal eden ölü girdiler için periyodik temizlik ya da süreye göre ikinci bir yapı (PriorityQueue/zaman çarkı). Zamanı test için enjekte etmek (Clock).

Takip sorusu 3: 20 pod'da aynı veriyi cache'liyorsun; veri değişince ne olur? Beklenen: pod'lar arası tutarsızlık; kısa TTL, Kafka ile invalidation ya da paylaşılan Redis (Redis'in allkeys-lru politikası örneklemeyle çalışan yaklaşık LRU'dur).

Benzer problemler

• LFU Cache (LeetCode 460)
• Insert Delete GetRandom O(1) (LeetCode 380)
• Design HashMap (LeetCode 706)
• All O'one Data Structure (LeetCode 432)
• Design Browser History (LeetCode 1472)