Live coding · Veri yapıları · Cache

LRU cache

OrtaHedef 20 dk

Klasik live coding sorusu

00:00/ 20:00 hedefÖnce kendin çöz; ipuçlarını sırayla aç.

Ürün detay servisinin önüne küçük bir in-memory cache konacak. Kapasite dolunca en uzun süredir kullanılmayan (Least Recently Used) eleman atılmalı. get ve put O(1) olmalı.

Görevler

  1. LruCache<K, V> sınıfını yaz: get(K) → Optional<V>, put(K, V), kapasite constructor'da.
  2. get de kullanım sayılır (erişilen eleman en yeni olur).
  3. Thread-safety'yi tartış ya da sağla.
  4. Mülakatçı "LinkedHashMap kullanmadan yap" derse: HashMap + çift yönlü bağlı liste ile yaz.
Başlangıç kodu
public class LruCache<K, V> {

    public LruCache(int capacity) {
    }

    public Optional<V> get(K key) {
        return Optional.empty();
    }

    public void put(K key, V value) {
    }
}
İpucu 1

LinkedHashMap(initialCapacity, loadFactor, accessOrder = true) erişim sırasını tutar; removeEldestEntry override edilerek kapasite aşımı yönetilir.

İpucu 2

Manuel: HashMap<K, Node> + head/tail sentinel'lı çift yönlü liste. get → node'u başa taşı; put → varsa güncelle ve başa taşı, yoksa ekle; kapasite aşıldıysa tail.prev'i sil.

İpucu 3

Thread-safety için en basiti metotları synchronized yapmak (LinkedHashMap'te get bile yapıyı değiştirir!). Production'da Caffeine.

Referans çözümü göster
Çözüm
// ===== 1) LinkedHashMap ile (mülakatta önce bunu söyle) =====
public class LruCache<K, V> {
    private final int capacity;
    private final LinkedHashMap<K, V> map;

    public LruCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(16, 0.75f, true) {          // accessOrder = true
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LruCache.this.capacity;
            }
        };
    }

    // accessOrder'da get() de yapıyı değiştirir; bu yüzden okuma da senkronize
    public synchronized Optional<V> get(K key) { return Optional.ofNullable(map.get(key)); }
    public synchronized void put(K key, V value) { map.put(key, value); }
}

// ===== 2) Manuel: HashMap + çift yönlü bağlı liste =====
public final class ManualLruCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);         // sentinel: en yeni tarafı
    private final Node<K, V> tail = new Node<>(null, null);         // sentinel: en eski tarafı

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

    public synchronized Optional<V> get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null) return Optional.empty();
        moveToFront(node);
        return Optional.of(node.value);
    }

    public synchronized void put(K key, V value) {
        Node<K, V> node = index.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }
        if (index.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            index.remove(lru.key);
        }
        Node<K, V> created = new Node<>(key, value);
        linkFirst(created);
        index.put(key, created);
    }

    private void moveToFront(Node<K, V> n) { unlink(n); linkFirst(n); }
    private void unlink(Node<K, V> n)      { n.prev.next = n.next; n.next.prev = n.prev; }
    private void linkFirst(Node<K, V> n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }

    private static final class Node<K, V> {
        final K key; V value; Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
}
// Her iki çözüm de "a, b ekle → a'yı oku → c ekle → b atılmalı" senaryosuyla test edildi.
Açıklama: neden böyle?
  • Neden iki yapı? HashMap O(1) arama, çift yönlü liste O(1) "başa taşı" ve "sondan sil" sağlar. Node'un key'i tutması, sondan silerken map'ten de silebilmek içindir.
  • Sentinel node'lar null kontrollerini ortadan kaldırır; kod kısalır ve hata riski azalır.
  • Thread-safety tuzağı: accessOrder=true LinkedHashMap'te get bile iç sırayı değiştirir. ReadWriteLock ile okumaları paralel yapmak yanlış olur.
  • Production: Caffeine (W-TinyLFU), LRU'dan daha iyi isabet oranı, eşzamanlılık, TTL, istatistik ve async yükleme sunar. Mülakatta "kendim yazmam, Caffeine kullanırım, ama mantığı şu" demek idealdir.
  • Varyasyon: TTL eklemek için node'a expiresAt eklenir ve get'te kontrol edilir; arka planda temizlik ya da lazy expiration yapılır.
  • LinkedHashMap(accessOrder=true) + removeEldestEntry ya da HashMap + çift yönlü liste
  • get erişimi sırayı günceller (başa taşıma)
  • Kapasite aşımında doğru elemanın atılması
  • O(1) karmaşıklık açıklaması
  • Thread-safety (synchronized) ve production'da Caffeine
  • Girdi kontrolü (kapasite > 0) ve test/örnek senaryo
  • TTL (5 dakika sonra geçersiz) eklesen nasıl yaparsın?
  • Bu cache 20 pod'da ayrı ayrı çalışıyor. Ürün fiyatı değişince ne olur? (invalidation, Kafka event, kısa TTL)
  • LRU yerine LFU ne zaman daha iyidir?