LFU cache

Problem

Sabit kapasiteli bir LFU (least frequently used) cache yaz:

• get(key): anahtar varsa değerini döndürür, yoksa -1.
• put(key, value): anahtarı ekler ya da günceller. Kapasite doluyken yeni bir anahtar eklenirse önce en az kullanılan anahtar atılır. Eşitlik varsa, aralarından en uzun süredir kullanılmayan (LRU) atılır.

Her anahtarın bir kullanım sayacı vardır: eklenince 1 olur, her get ve her güncelleyen put 1 artırır. İki işlem de ortalama O(1) olmalı.

cache = LFUCache(2)
put(1, 10); put(2, 20)       frekans: 1->1, 2->1
get(1)       -> 10           frekans: 1->2, 2->1
put(3, 30)   -> 2 atılır (frekans 1, en düşük)
get(2)       -> -1
get(3)       -> 30           frekans: 1->2, 3->2
put(4, 40)   -> eşitlik (ikisi de 2); 1 daha uzun süredir kullanılmadı, 1 atılır
get(1)       -> -1

Netleştirme soruları

• Güncelleyen put frekansı artırır mı? (Evet.)
• Eşitlikte kural LRU mu? (Evet.)
• Kapasite 0 olabilir mi? (Eski LeetCode testlerinde vardı; o zaman put hiçbir şey yapmaz. Çözüm bunu desteklemeli.)
• Frekanslar zamanla azalmalı mı (aging)? (Bu problemde hayır; production'da önemli bir konudur.)

İpuçları

Yaklaşım

Kaba çözüm: Her anahtar için (değer, frekans, son kullanım zamanı) tut; tahliyede tümünü tarayıp en küçük (frekans, zaman) ikilisini bul. get O(1), tahliye O(n). Testlerde referans olarak kullanıldı.

Heap: (frekans, zaman) sıralı bir PriorityQueue; ama her get frekansı değiştirir ve güncelleme en iyi ihtimalle O(log n)'dir.

Frekans kovaları (seçilen çözüm): Üç yapı:

1. entries: key -> (value, frequency)
2. keysByFrequency: frequency -> LinkedHashSet<key>; her kova kendi içinde LRU sırasıyla (en eski başta).
3. minFrequency: en düşük dolu kova.

İşlemler:

• touch(key) (her kullanımda): anahtarı eski frekans kovasından sil; kova boşaldıysa map'ten kaldır ve gerekirse minFrequency'yi artır; frekansı artır; yeni kovanın sonuna ekle.
• evict: keysByFrequency.get(minFrequency)'nin ilk elemanı (o frekanstaki en eski) atılır.
• put (yeni anahtar): doluysa önce evict; sonra frekans 1 kovasına ekle, minFrequency = 1.

Neden minFrequency++ yeterli? minFrequency sadece iki şekilde değişir: yeni anahtar eklenince 1 olur; ya da en düşük kovadaki son anahtar kullanılınca boşalır, o anahtar minFrequency + 1 kovasına geçer ve o kova artık kesinlikle dolu ve en düşüktür. Tahliye sonrası ise her zaman yeni bir anahtar eklenir ve minFrequency zaten 1 yapılır; bu yüzden tahliyede minimumu yeniden aramaya gerek yoktur.

LinkedHashMap/LinkedHashSet alternatifi ve manuel liste: LinkedHashSet, içeride LinkedHashMap kullanır: O(1) add, remove, ve ekleme sırasıyla iterasyon verir; yani her kova aslında küçük bir LRU listesidir. Mülakatçı "hazır yapı kullanma" derse her kova için LRU Cache'teki gibi sentinel'lı çift yönlü liste yazılır ve map key -> Node (Node içinde değer ve frekans) olur. LRU'nun aksine tek bir LinkedHashMap(accessOrder = true) LFU'yu çözmez, çünkü sıralama kriteri frekanstır.

Java çözümü

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

public final class LFUCache {

    private static final class Entry {
        int value;
        int frequency = 1;
        Entry(int value) { this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Entry> entries = new HashMap<>();
    // frekans -> o frekanstaki anahtarlar, en eski kullanılandan en yeniye (LinkedHashSet ekleme sırasını korur)
    private final Map<Integer, LinkedHashSet<Integer>> keysByFrequency = new HashMap<>();
    private int minFrequency = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Entry entry = entries.get(key);
        if (entry == null) return -1;
        touch(key, entry);
        return entry.value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        Entry entry = entries.get(key);
        if (entry != null) {
            entry.value = value;
            touch(key, entry);                            // güncelleme de kullanım sayılır
            return;
        }
        if (entries.size() == capacity) evict();
        entries.put(key, new Entry(value));
        keysByFrequency.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFrequency = 1;                                 // yeni gelen anahtarın frekansı her zaman en düşüktür
    }

    /** Anahtarı frekans kovasından bir üstüne taşır. */
    private void touch(int key, Entry entry) {
        int oldFrequency = entry.frequency;
        LinkedHashSet<Integer> bucket = keysByFrequency.get(oldFrequency);
        bucket.remove(key);
        if (bucket.isEmpty()) {
            keysByFrequency.remove(oldFrequency);
            if (minFrequency == oldFrequency) minFrequency++;   // en düşük kova boşaldı: yeni minimum bir üstü
        }
        entry.frequency++;
        keysByFrequency.computeIfAbsent(entry.frequency, f -> new LinkedHashSet<>()).add(key);
    }

    /** En düşük frekanslı kovadaki en eski anahtarı atar (eşitlikte LRU). */
    private void evict() {
        LinkedHashSet<Integer> bucket = keysByFrequency.get(minFrequency);
        int victim = bucket.iterator().next();
        bucket.remove(victim);
        if (bucket.isEmpty()) keysByFrequency.remove(minFrequency);
        entries.remove(victim);
    }
}

Karmaşıklık

• Zaman: get ve put ortalama O(1). Tüm işlemler hash map/set işlemleridir; iterator().next() bir LinkedHashSet'te ilk elemanı O(1)'de verir.
• Bellek: O(capacity); her anahtar bir girdi ve bir kovada bir kayıt. Boş kovalar silindiği için kova sayısı da O(capacity) ile sınırlıdır.

Kenar durumlar ve testler

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

• Yukarıdaki senaryo: en düşük frekans atılıyor; eşitlikte LRU atılıyor.
• Kapasite 0: put etkisiz, get -1.
• Kapasite 1: frekansı 3 olan anahtar bile yeni anahtar gelince atılıyor (yer açmak için tek aday odur).
• Güncelleyen put frekansı artırıyor; bu yüzden diğer anahtar atılıyor ve güncellenen değer korunuyor.
• 200 tur × 1.000 rastgele işlem (kapasite 0-4, anahtar 0-7): her get sonucu, (frekans, son kullanım) ile O(n) tahliye yapan naif referansla aynı.

Mülakatçı için

LFU, LRU'yu bilen adayı zorlamak için kullanılır; 40 dakikada çalışan bir çözüm güçlü bir sonuçtur. Gözlemle: aday üç yapının rolünü kodlamadan önce açıklıyor mu? minFrequency güncellemesinin neden sadece "boşalan kova minimumsa" yapıldığını gerekçelendirebiliyor mu? Eşitlikte LRU sırasını nasıl koruyor? Kapasite 0'ı düşünüyor mu?

Thread-safety takip sorusu: LRU'daki tartışmanın aynısı, daha ağır haliyle: her get iki kovayı ve bir sayacı değiştirir; bu yüzden işlem bütün olarak atomik olmalıdır. En basit doğru çözüm metotları synchronized yapmaktır; ReadWriteLock ile get'i okuma kilidine almak yanlıştır, çünkü get yapıyı değiştirir. Ölçeklenebilir çözüm, frekansları kesin değil yaklaşık tutmaktır: Caffeine'in W-TinyLFU politikası frekansları 4-bit'lik bir Count-Min Sketch'te tutar, okumaları buffer'layıp toplu uygular ve periyodik olarak tüm sayaçları yarıya indirerek (aging) eski popüler anahtarların cache'i işgal etmesini önler.

İpucu zamanlaması: Aday 8-10 dakikada frekans kovası fikrine ulaşamazsa ilk ipucunu ver. minFrequency'yi her tahliyede tüm kovaları tarayarak bulursa (O(n)), çalışmasına izin ver, sonra "bunu O(1) yapabilir misin?" diye sor. Yapıyı kurup minFrequency güncellemesinde takılırsa üçüncü ipucunu ver.

Takip sorusu 1: Frekanslar sonsuza kadar büyüyor; dün çok popüler olan ama artık kullanılmayan bir anahtar cache'te kalıyor. Ne yaparsın? Beklenen: aging (periyodik olarak sayaçları yarıya indirmek), pencereli frekans ya da LRU ile LFU'yu birleştiren politikalar (W-TinyLFU, ARC).

Takip sorusu 2: LRU mu LFU mu seçersin? Beklenen: iş yüküne bağlı. Taramaya (bir kez okunan çok sayıda anahtar) karşı LFU dirençlidir, LRU bu durumda cache'i boşaltır; ani popülerlik değişimlerine LRU daha hızlı uyum sağlar. Ölçüm (hit ratio) olmadan karar verilmez.

Benzer problemler

• LRU Cache (LeetCode 146)
• All O'one Data Structure (LeetCode 432)
• Insert Delete GetRandom O(1) (LeetCode 380)
• Design In-Memory File System (LeetCode 588)
• Maximum Frequency Stack (LeetCode 895)