Live coding algoritmaları: rate limiter, LRU, aralıklar ve top-K

Bu bölümde

Backend live coding'inde algoritma soruları genelde LeetCode bulmacası gibi değil, bir iş senaryosunun içinde gelir: "kupon endpoint'ine kullanıcı başına limit koy", "ürün detayının önüne küçük bir cache yaz", "kampanya dönemlerini birleştir", "en çok satan 10 ürünü bul". Bu bölümde soruya nasıl yaklaşacağını, Java koleksiyonlarının gerçek maliyetlerini ve bu dört klasik sorunun (k7-k10) çalışan, test edilmiş çözümlerini; ardından sık gelen kalıpları (two-sum, sliding window, iki işaretçi, BFS/DFS, binary search, parantez, anagram) öğreneceksin. Bölümdeki tüm Java kodları JDK 21 ile derlenip testlerle çalıştırıldı; Lua script'leri Redis 7.0 üzerinde denendi.

Konu anlatımı

Algoritma sorusuna yaklaşım: altı adım

Mülakatçı doğru cevaptan çok nasıl düşündüğünü izler. Şu sırayı her soruda sesli uygula:

1. Netleştir. Girdi ne kadar büyük? Boş olabilir mi, null gelir mi? Eşitlikte ne olur? Sonuç sıralı mı olmalı? Thread-safe olmalı mı? "Ardışık kampanya günleri birleşsin mi?" gibi sorular iş kuralıdır; varsayma, sor.
2. Örnek üzerinden geç. Verilen örneği elle çöz, bir de kenar durum örneği üret (boş liste, tek eleman, iç içe aralık). Bu adım yanlış anladığın gereksinimi kod yazmadan yakalar.
3. Brute force'u söyle. "En basit çözüm her çifti karşılaştırmak, O(n²)." Yazmak zorunda değilsin; söylemek hem bir taban çizgisi verir hem de soruyu anladığını gösterir.
4. İyileştir. Darboğazı adlandır: "Tekrar tekrar arama yapıyorum, HashMap ile O(1)'e indirebilirim", "Sıralarsam tek geçiş yeter". İyileştirmenin bedelini de söyle: ek bellek, girdiyi değiştirme, okunabilirlik.
5. Kodla ve karmaşıklığı söyle. Zaman ve bellek; ortalama ve en kötü durum ayrı ise ikisini de.
6. Test et. Önce verilen örneği koddan elle geçir (dry run), sonra kenar durumlarını. Mümkünse küçük bir JUnit testi ya da main içinde assert yaz.

Kalıp cümleler: "Let me restate the problem...", "A brute-force approach would be..., which is O(n²). We can do better by...", "The bottleneck is...", "Let me walk through the example with my code."

Big-O kısa tekrar

Big-O, girdi büyüdükçe maliyetin nasıl büyüdüğünü anlatır; sabit çarpanları ve küçük terimleri atar.

Üç kavram mülakatta sık karışır:

• Amortize maliyet: ArrayList.add çoğu zaman O(1), dizi dolunca kapasiteyi büyütüp tüm elemanları kopyalar (O(n)). Büyüme oranı sabit bir çarpan olduğu için (OpenJDK'da yaklaşık 1,5 kat) n ekleme toplamda O(n) tutar; işlem başına amortize O(1).
• Ortalama ve en kötü durum: HashMap ortalama O(1)'dir; kötü hash fonksiyonu ile tüm anahtarlar aynı bucket'a düşerse en kötü durum ortaya çıkar (Java 8+ bunu treeify ile sınırlar, aşağıya bak). Quickselect ortalama O(n), en kötü O(n²).
• Bellek de bir maliyettir: "O(n) ek bellekle O(n) zamana indirdim" bir trade-off cümlesidir. Milyonlarca kullanıcılı bir rate limiter'da kullanıcı başına 8 byte ile 800 byte arasındaki fark, bir sunucuyla on sunucu arasındaki farktır.

Java koleksiyonlarının karmaşıklıkları

Mülakatta sorulan iç detaylar:

• HashMap nasıl çalışır? hashCode() sonucu üst bitlerle karıştırılır (h ^ (h >>> 16)), (n - 1) & hash ile bucket seçilir (kapasite 2'nin kuvveti). Çakışan anahtarlar bucket içinde bağlı listede tutulur; bir bucket'taki eleman sayısı 8'i geçerse ve tablo kapasitesi en az 64 ise liste kırmızı-siyah ağaca dönüşür (treeify), böylece en kötü durum O(n) yerine O(log n) olur. Eleman sayısı kapasite × load factor'ı (varsayılan 0,75) aşınca tablo iki katına büyür ve tüm elemanlar yeniden dağıtılır.
• equals/hashCode sözleşmesi: Mutable bir alanı hashCode'da kullanan nesneyi map'e koyup sonra o alanı değiştirirsen nesne yanlış bucket'ta kalır ve bir daha bulunamaz. Anahtarlar immutable olmalı; record bunun için idealdir.
• PriorityQueue neden sıralı yazdırılmaz? Heap sadece "ebeveyn ≤ çocuk" kuralını garanti eder; dizinin kendisi sıralı değildir. Sıralı çıktı için poll ile boşaltmak gerekir.
• Stack için ne kullanırsın? ArrayDeque (push/pop). java.util.Stack, Vector'dan türer ve her metodu synchronized'dır; Javadoc da Deque kullanılmasını önerir.

Rate limiter (k7)

Kupon doğrulama endpoint'i bot saldırısı altında; her kullanıcı dakikada en fazla 5 istek atabilmeli. Önce algoritma seçimi:

Token bucket ile leaky bucket'ın "sayaç" (meter) versiyonu matematiksel olarak eşdeğerdir; fark, leaky bucket'ın kuyruk versiyonunun isteği reddetmek yerine geciktirmesidir. API rate limiting'de genelde reddetmek (429) istenir; bu yüzden token bucket en sık seçilen algoritmadır.

Lazy refill. Her kullanıcı için arka planda token ekleyen bir zamanlayıcı çalıştırmak milyonlarca kullanıcıda imkansızdır. Bunun yerine son dolum zamanını saklarsın ve istek geldiğinde "o zamandan beri kaç token birikti?" sorusunu hesaplarsın. Hiç istek atmayan kullanıcı sıfır CPU harcar.

public final class TokenBucketRateLimiter {

    private final long capacity;
    private final long nanosPerToken;                  // 60 sn / 5 = 12 sn'de bir token
    private final LongSupplier nanoClock;              // test edilebilirlik için enjekte
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketRateLimiter(long capacity, Duration period, LongSupplier nanoClock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.nanosPerToken = period.toNanos() / capacity;
        this.nanoClock = nanoClock;
    }

    public boolean tryAcquire(String key) {
        Bucket b = buckets.computeIfAbsent(key, k -> new Bucket(capacity, nanoClock.getAsLong()));
        synchronized (b) {                             // sadece bu kullanıcının kovası kilitlenir
            long now = nanoClock.getAsLong();
            long newTokens = (now - b.lastRefill) / nanosPerToken;
            if (newTokens > 0) {
                b.tokens = Math.min(capacity, b.tokens + newTokens);
                // Kova dolduysa birikmiş artık süreyi at; dolmadıysa kesirli kısmı kaybetme
                b.lastRefill = b.tokens == capacity ? now : b.lastRefill + newTokens * nanosPerToken;
            }
            if (b.tokens > 0) {
                b.tokens--;
                return true;
            }
            return false;
        }
    }

    private static final class Bucket {
        long tokens;
        long lastRefill;
        Bucket(long tokens, long lastRefill) { this.tokens = tokens; this.lastRefill = lastRefill; }
    }
}

Neden map'in thread-safe olması yetmez? ConcurrentHashMap sadece map işlemlerini (bul, ekle) atomik yapar. Kovanın "oku → hesapla → yaz" adımları üç ayrı işlemdir; iki thread aynı anda 1 token görüp ikisi de izin verebilir. Bu yüzden kova güncellemesi ayrıca atomik olmalı. Kilit kullanıcı başına olduğu için farklı kullanıcılar birbirini beklemez; contention sadece aynı kullanıcının eşzamanlı isteklerinde olur.

Tamsayı aritmetiği neden? Kata çözümü token'ı double ve "nano başına token" oranıyla tutuyor. Bu, bazı kapasite/periyot kombinasyonlarında birikimin tam sınırda 0.9999999 çıkmasına ve token'ın bir istek geç verilmesine yol açar (1-1000 arası kapasite ve 1/7/60/3600 saniyelik periyotlarla, periyodun kapasiteye tam bölündüğü kombinasyonlar denendiğinde 20'sinde görüldü). "Token başına nanosaniye" ile tamsayı bölme bu hatayı ortadan kaldırır.

Kilitsiz alternatif: GCRA ve CAS. Generic Cell Rate Algorithm, token bucket'ı tek bir sayı ile ifade eder: TAT (theoretical arrival time), yani kova tamamen boşalmış sayılacağı an. İzin vermek, TAT'ı bir aralık (T) ileri itmektir; TAT şimdiden capacity × T kadar ilerideyse kova doludur. Tek bir long olduğu için AtomicLong.compareAndSet ile kilitsiz güncellenir:

public final class GcraRateLimiter {

    private final long emissionInterval;               // T: iki token arası süre
    private final long burstWindow;                    // capacity * T
    private final LongSupplier nanoClock;
    private final ConcurrentHashMap<String, AtomicLong> tats = new ConcurrentHashMap<>();

    public GcraRateLimiter(long capacity, Duration period, LongSupplier nanoClock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.emissionInterval = period.toNanos() / capacity;
        this.burstWindow = emissionInterval * capacity;
        this.nanoClock = nanoClock;
    }

    public boolean tryAcquire(String key) {
        AtomicLong tat = tats.computeIfAbsent(key, k -> new AtomicLong(nanoClock.getAsLong()));
        while (true) {
            long now = nanoClock.getAsLong();
            long current = tat.get();
            long newTat = Math.max(current, now) + emissionInterval;
            if (newTat - now > burstWindow) return false;          // kova dolu: reddet
            if (tat.compareAndSet(current, newTat)) return true;   // yarışı kaybettiysek tekrar dene
        }
    }
}

synchronized mı CAS mı? Düşük contention'da ikisi de hızlıdır; modern JVM'de kısa, yarışmasız bir synchronized blok ucuzdur. CAS, yüksek contention'da thread'leri park etmez ama başarısız denemelerde CPU harcar (spin). Java 21 virtual thread'lerde synchronized içinde bloklayan bir işlem carrier thread'i sabitler (pinning; JDK 24 ile JEP 491 bunu büyük ölçüde giderdi), ama burada kilit içinde bloklayan işlem yok. Mülakatta "önce okunabilir olan synchronized ile yazarım, ölçüm contention gösterirse GCRA/CAS'e geçerim" demek doğru dengedir. Yukarıdaki token bucket ve GCRA implementasyonları, 16 thread'den gelen 1000 eşzamanlı istekte kapasite 100 iken tam 100 izin verdi.

Zamanı enjekte et. System.nanoTime()'ı doğrudan çağıran kod, "12 saniye sonra bir token gelir" davranışını test etmek için Thread.sleep gerektirir: yavaş ve flaky. LongSupplier nanoClock (ya da java.time.Clock) enjekte edip testte sahte saati ilerletirsin. Rate limiting gibi süre ölçen işlerde monoton bir saat (nanoTime) kullanılır; duvar saati (Clock.systemUTC()) NTP düzeltmesiyle geri gidebilir.

class TokenBucketRateLimiterTest {

    private final AtomicLong now = new AtomicLong();
    private final TokenBucketRateLimiter limiter =
            new TokenBucketRateLimiter(5, Duration.ofMinutes(1), now::get);

    @Test
    void allowsCapacityThenRejects() {
        for (int i = 0; i < 5; i++) assertThat(limiter.tryAcquire("u1")).isTrue();
        assertThat(limiter.tryAcquire("u1")).isFalse();
        assertThat(limiter.tryAcquire("u2")).isTrue();            // kullanıcılar bağımsız
    }

    @Test
    void refillsOneTokenPerInterval() {
        for (int i = 0; i < 5; i++) limiter.tryAcquire("u1");
        now.addAndGet(Duration.ofSeconds(12).toNanos());
        assertThat(limiter.tryAcquire("u1")).isTrue();
        assertThat(limiter.tryAcquire("u1")).isFalse();
    }

    @Test
    void neverExceedsCapacityAfterLongIdle() {
        now.addAndGet(Duration.ofHours(1).toNanos());
        for (int i = 0; i < 5; i++) assertThat(limiter.tryAcquire("u1")).isTrue();
        assertThat(limiter.tryAcquire("u1")).isFalse();
    }
}

Bellek. ConcurrentHashMap hiç küçülmez: bir gün boyunca 5 milyon farklı kullanıcı gelirse 5 milyon kova bellekte kalır. Çözüm: boşta kalan kovaları silmek. Caffeine'de expireAfterAccess(period) ile kova bir periyot kullanılmazsa atılır; atılan kova zaten dolu sayılacağı için davranış değişmez.

Dağıtık versiyon. 10 pod'un her biri kendi sayacını tutarsa kullanıcı 10 kat limit alır (load balancer istekleri dağıttığı için). State'in tek bir yerde olması gerekir: Redis. Kritik nokta atomiklik: GET → hesapla → SET üç ayrı komut olursa iki pod aynı anda okuyup ikisi de izin verir. Redis bir Lua script'ini atomik çalıştırır (script çalışırken başka komut işlenmez), bu yüzden tüm token bucket mantığı tek script'e konur:

-- KEYS[1] = rl:{userId}   ARGV[1] = capacity   ARGV[2] = ms per token
local capacity = tonumber(ARGV[1])
local msPerToken = tonumber(ARGV[2])
local t = redis.call('TIME')                       -- sunucu saati: pod'lar arası saat farkı yok
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts = tonumber(state[2]) or now

local refill = math.floor((now - ts) / msPerToken)  -- lazy refill
if refill > 0 then
  tokens = math.min(capacity, tokens + refill)
  if tokens == capacity then ts = now else ts = ts + refill * msPerToken end
end

local allowed = 0
if tokens > 0 then
  tokens = tokens - 1
  allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', ts)
redis.call('PEXPIRE', KEYS[1], capacity * msPerToken)  -- boşta kalan kullanıcı kendiliğinden silinir
return allowed

Ayrıntılar: Anahtar adı KEYS ile verilir (Redis dokümantasyonu, cluster'da doğru çalışması için script'in eriştiği tüm anahtarların argüman olarak geçilmesini şart koşar). PEXPIRE bellek problemini Redis tarafında çözer. Script SCRIPT LOAD ile bir kez yüklenip EVALSHA ile çağrılır. Fixed window ise iki satırdır: INCR ve sayaç 1 ise PEXPIRE; ikisinin aynı script'te olması, INCR sonrası process çökerse TTL'siz kalıcı bir sayaç oluşmasını önler.

Production soruları: Redis'e her istekte gitmek ~1 ms ağ gecikmesi ekler; yük çok yüksekse lokal bir ön limit (pod başına limit / pod sayısı) ile Redis'e giden trafik azaltılır. Redis erişilemezse fail-open mı (izin ver) fail-closed mı (reddet)? Kupon doğrulama gibi kötüye kullanıma açık bir endpoint'te fail-closed, ürün listeleme gibi bir endpoint'te fail-open mantıklıdır. Reddedilen istek 429 Too Many Requests ve Retry-After ile döner. Hazır çözümler: Bucket4j (Java, token bucket, Redis/Hazelcast backend'leri), Spring Cloud Gateway RedisRateLimiter (token bucket), Nginx/Envoy seviyesinde limit.

LRU cache (k8)

Kapasite dolunca en uzun süredir kullanılmayan eleman atılır; get ve put O(1) olmalı. İki ihtiyaç var: anahtarla O(1) arama (hash map) ve O(1) "en yeniye taşı / en eskiyi sil" (çift yönlü bağlı liste). İki yapıyı birleştirmek gerekir.

1) LinkedHashMap ile. LinkedHashMap girdilerini bir çift yönlü listede de tutar. 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:

public final class LruCache<K, V> {

    private final Map<K, V> map;

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

    // accessOrder'da get() de iç listeyi 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. Mülakatçı "LinkedHashMap kullanmadan yaz" derse:

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) {                    // güncelleme de "kullanım" sayılır
            node.value = value;
            moveToFront(node);
            return;
        }
        if (index.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            index.remove(lru.key);             // node'un key'i tutmasının nedeni bu
        }
        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; }
    }
}

Sentinel node'lar (head, tail) listenin hiçbir zaman boş olmamasını sağlar; "ilk eleman mı, son eleman mı" null kontrolleri ortadan kalkar ve pointer hatası riski azalır. Manuel versiyon, 100.000 rastgele get/put işleminde LinkedHashMap versiyonuyla birebir aynı sonuçları verdi.

Thread-safety tuzağı. accessOrder = true olan bir LinkedHashMap'te get yazma işlemidir: girdiyi listenin sonuna taşır. Bu yüzden ReadWriteLock ile okumaları paralel yapmak listeyi bozar. Collections.synchronizedMap ya da synchronized metotlar doğrudur ama tüm cache'i tek kilide bağlar; yüksek eşzamanlılıkta darboğaz olur. Production'da cevap Caffeine'dir: Window TinyLFU politikası çoğu iş yükünde LRU'dan daha yüksek isabet oranı verir, okumaları kilitlemeden ring buffer'lara kaydeder ve toplu uygular, TTL (expireAfterWrite), boyut sınırı, istatistik ve asenkron yükleme sunar. Mülakat cümlesi: "Production'da bunu kendim yazmam, Caffeine kullanırım; ama mantığı şu."

TTL eklemek. Node'a expiresAt eklenir, get'te süresi geçmişse silinip empty dönülür (lazy expiration). Hiç okunmayan süresi geçmiş girdiler kapasiteyi işgal etmesin diye ya kapasite dolduğunda temizlik yapılır ya da periyodik bir temizleyici çalışır.

Aralıkları birleştirme (k9)

Bir satıcının kampanya dönemleri farklı ekiplerden çakışık geliyor; takvimde birleştirilmiş hali gösterilecek. Dönemler gün bazında ve iki ucu dahil; ardışık dönemler de birleşir (1-3 Kasım + 4-6 Kasım = 1-6 Kasım).

Brute force: her dönemi diğer tümüyle karşılaştırıp birleştirmek, değişiklik kalmayana kadar tekrarlamak; O(n²) ve üstü. Anahtar gözlem: başlangıca göre sıralarsan, bir dönemle çakışabilecek dönemler listede hemen ardından gelir. Tek geçişte "şu anki birleşik dönem" tutulur:

record Period(LocalDate start, LocalDate end) {
    Period {
        Objects.requireNonNull(start);
        Objects.requireNonNull(end);
        if (end.isBefore(start)) throw new IllegalArgumentException("end before start");
    }
}

static List<Period> merge(List<Period> periods) {
    if (periods.isEmpty()) return List.of();
    List<Period> sorted = new ArrayList<>(periods);                 // girdiyi değiştirme
    sorted.sort(Comparator.comparing(Period::start));

    List<Period> merged = new ArrayList<>();
    Period current = sorted.get(0);
    for (int i = 1; i < sorted.size(); i++) {
        Period next = sorted.get(i);
        if (!next.start().isAfter(current.end().plusDays(1))) {    // çakışıyor ya da bitişik
            LocalDate end = next.end().isAfter(current.end()) ? next.end() : current.end();
            current = new Period(current.start(), end);
        } else {
            merged.add(current);
            current = next;
        }
    }
    merged.add(current);
    return merged;
}

Üç kritik nokta: (1) bitişiklik kuralı start <= current.end + 1 gün; iki ucu dahil gün bazlı olduğu için +1. Saat bazlı yarı açık aralıklarda ([10:00, 12:00)) kural next.start <= current.end olur. (2) İç içe dönem: 1-10 ile 2-3 birleşirken bitiş max ile alınmazsa 1-3'e küçülür. (3) Kopyasını sırala; çağıranın listesini değiştirmek (ya da List.of ile gelen immutable listeyi sıralamaya çalışıp UnsupportedOperationException almak) klasik bir hatadır. Karmaşıklık: sıralama O(n log n), geçiş O(n), toplam O(n log n) zaman, O(n) bellek. Record'un compact constructor'ı geçersiz dönemi (bitiş < başlangıç) oluşturma anında reddeder.

Takip sorusu: aynı anda en fazla kaç kampanya aktif? Sweep line: her başlangıç +1, her bitişin ertesi günü -1; olayları zamana göre sıralayıp toplamın maksimumunu al. TreeMap hem sıralamayı hem aynı gündeki olayların toplanmasını sağlar:

static int maxConcurrent(List<Period> periods) {
    TreeMap<LocalDate, Integer> delta = new TreeMap<>();
    for (Period p : periods) {
        delta.merge(p.start(), 1, Integer::sum);
        delta.merge(p.end().plusDays(1), -1, Integer::sum);         // iki uç dahil: ertesi gün düşer
    }
    int active = 0, max = 0;
    for (int d : delta.values()) {
        active += d;
        max = Math.max(max, active);
    }
    return max;
}

Aynı kalıp toplantı odası sayısı, depo kapasite planlaması ve kargo teslimat pencerelerinde karşına çıkar. Dönemler veritabanındaysa aynı problem SQL'de window function'larla "gaps and islands" olarak çözülür (bkz. Bölüm 9).

Top-K (k10)

Günün sipariş satırlarından toplam adede göre en çok satan K ürün; eşit adette küçük productId önce; bir ürün birden çok satırda geçebilir.

İki aşama var: önce ürün başına toplam (HashMap.merge, O(n)), sonra m farklı ürün içinden en iyi K'yı seçmek.

Seçenek 1, sırala ve ilk K'yı al: O(m log m). m küçükse en okunabilir çözüm budur:

static List<Long> topKSorted(List<OrderLine> lines, int k) {
    if (k <= 0) return List.of();
    return lines.stream()
            .collect(Collectors.groupingBy(OrderLine::productId, Collectors.summingLong(OrderLine::quantity)))
            .entrySet().stream()
            .sorted(Map.Entry.<Long, Long>comparingByValue().reversed()
                    .thenComparing(Map.Entry.comparingByKey()))
            .limit(k)
            .map(Map.Entry::getKey)
            .toList();
}

Seçenek 2, boyutu K olan min-heap: O(m log k) zaman, O(k) ek bellek. Heap'in tepesinde şimdiye kadarki en kötü aday durur; yeni aday ondan iyiyse tepe atılır. k = 10, m = 1.000.000 için log k ≈ 3,3 ile log m ≈ 20 arasındaki fark ve tüm listeyi sıralamak yerine 10 elemanlık heap tutmak önemlidir.

static List<Long> topK(List<OrderLine> lines, int k) {
    if (k <= 0) return List.of();
    Map<Long, Long> totals = new HashMap<>();
    for (OrderLine line : lines) totals.merge(line.productId(), (long) line.quantity(), Long::sum);

    // Tepede "en kötü" aday: adedi küçük olan; eşitlikte id'si BÜYÜK olan
    Comparator<Map.Entry<Long, Long>> worstFirst = Map.Entry.<Long, Long>comparingByValue()
            .thenComparing(Map.Entry.<Long, Long>comparingByKey().reversed());
    PriorityQueue<Map.Entry<Long, Long>> heap = new PriorityQueue<>(worstFirst);
    for (Map.Entry<Long, Long> e : totals.entrySet()) {
        heap.offer(e);
        if (heap.size() > k) heap.poll();
    }
    List<Long> result = new ArrayList<>(heap.size());
    while (!heap.isEmpty()) result.add(heap.poll().getKey());      // kötüden iyiye
    Collections.reverse(result);                                    // iyiden kötüye
    return result;
}

Bu sorunun en çok hata yapılan yeri comparator'dır. Yazmadan önce "heap'in tepesinde kim durmalı?" sorusunu cevapla: atılacak olan, yani adedi en küçük olan; eşitlikte sonuçta sonra gelmesi gereken, yani id'si büyük olan. Bu yüzden ikinci kriter comparingByKey().reversed().

Seçenek 3, quickselect: Quicksort'un partition adımıyla K'ıncı elemanın yerini bulur; ortalama O(m), en kötü O(m²) (rastgele pivot bunu olasılıksal olarak önler). Sonuç ilk K'yı sırasız verir; istenirse K eleman ayrıca sıralanır (O(k log k)). Diziyi yerinde değiştirir.

Seçenek 4, bucket: Adetlerin üst sınırı küçükse (ör. adet ≤ n), adede göre kovalar kurulur ve en yüksek kovadan geriye doğru K eleman toplanır: O(n + m). Adet aralığı büyükse bellek patlar.

Yukarıdaki heap ve sıralama versiyonları 300 rastgele girdide birebir aynı sonucu verdi. Kenar durumları: k <= 0 boş liste; k farklı ürün sayısından büyükse tüm ürünler; quantity'leri long'da topla, int taşabilir.

Gerçek sistemde top-K bir stream problemidir: gün boyu akan sipariş event'leri Kafka Streams/Flink ile pencereli olarak sayılır ya da Redis Sorted Set'te ZINCRBY products:sales:2026-10-21 <adet> <productId> ile tutulup ZREVRANGE ... 0 9 WITHSCORES ile okunur. Çok yüksek kardinalitede kesinlik bellekle takas edilir: Count-Min Sketch ile yaklaşık sayım + küçük bir heap.

Sık gelen kalıplar

Two-sum (hash map ile tamamlayıcıyı ara). "Bütçeyi tam dolduran iki ürün": brute force O(n²); her elemanda budget - fiyat daha önce görüldü mü diye bakmak O(n) zaman, O(n) bellek.

static Optional<int[]> twoSum(int[] prices, int budget) {
    Map<Integer, Integer> seen = new HashMap<>();                   // değer -> index
    for (int i = 0; i < prices.length; i++) {
        Integer j = seen.get(budget - prices[i]);
        if (j != null) return Optional.of(new int[]{j, i});
        seen.put(prices[i], i);                                     // kendisiyle eşleşmesin diye sonra ekle
    }
    return Optional.empty();
}

Sliding window (kayan pencere). Ardışık bir alt dizi hakkında soru varsa (en uzun, en kısa, en büyük toplam), pencerenin iki ucunu tek yönde ilerletirsin; her eleman en fazla bir kez girer, bir kez çıkar: O(n).

// Değişken pencere: tekrar eden karakter içermeyen en uzun alt dizi
static int longestUniqueSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        Integer prev = lastSeen.put(s.charAt(right), right);
        if (prev != null && prev >= left) left = prev + 1;          // pencereyi daralt
        best = Math.max(best, right - left + 1);
    }
    return best;
}

// Sabit pencere: k ardışık günün en yüksek cirosu
static long maxWindowSum(long[] daily, int k) {
    if (k <= 0 || k > daily.length) throw new IllegalArgumentException("invalid k");
    long sum = 0;
    for (int i = 0; i < k; i++) sum += daily[i];
    long best = sum;
    for (int i = k; i < daily.length; i++) {
        sum += daily[i] - daily[i - k];                             // giren - çıkan
        best = Math.max(best, sum);
    }
    return best;
}

prev >= left kontrolü önemlidir: "abba"da ikinci a görüldüğünde önceki a zaten pencere dışındadır; kontrol olmadan left geriye kayar.

İki işaretçi. Sıralı veride iki uçtan ya da aynı yönde iki hızla ilerlemek, iç içe döngüyü tek geçişe indirir:

static Optional<int[]> pairWithSumSorted(int[] sorted, int target) {
    int i = 0, j = sorted.length - 1;
    while (i < j) {
        int sum = sorted[i] + sorted[j];
        if (sum == target) return Optional.of(new int[]{i, j});
        if (sum < target) i++; else j--;                            // toplamı büyüt ya da küçült
    }
    return Optional.empty();
}

Sıralı dizide hash map yerine iki işaretçi O(1) ek bellekle çalışır; sıralı değilse sıralamak O(n log n) ekler, bu durumda hash map'li two-sum daha iyidir.

BFS ve DFS. BFS katman katman ilerler; ağırlıksız grafikte en kısa yolu bulur (ArrayDeque kuyruk). DFS derinliğe iner; erişilebilirlik, bileşen sayma, ağaç dolaşma için. Her ikisinde de ziyaret edildi işareti olmazsa döngülü grafikte sonsuza girersin.

// Depo ızgarasında (0 boş, 1 raf) en kısa yol uzunluğu
static int shortestPath(int[][] grid, int sr, int sc, int tr, int tc) {
    int rows = grid.length, cols = grid[0].length;
    if (grid[sr][sc] == 1 || grid[tr][tc] == 1) return -1;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);
    ArrayDeque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{sr, sc});
    dist[sr][sc] = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        if (cur[0] == tr && cur[1] == tc) return dist[tr][tc];
        for (int[] d : dirs) {
            int r = cur[0] + d[0], c = cur[1] + d[1];
            if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 0 && dist[r][c] == -1) {
                dist[r][c] = dist[cur[0]][cur[1]] + 1;              // kuyruğa eklerken işaretle
                queue.add(new int[]{r, c});
            }
        }
    }
    return -1;
}

// Kategori ağacında bir kategorinin tüm alt kategorileri: iteratif DFS, döngüye dayanıklı
static Set<String> descendants(Map<String, List<String>> children, String root) {
    Set<String> visited = new LinkedHashSet<>();
    ArrayDeque<String> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        String cur = stack.pop();
        if (!visited.add(cur)) continue;                            // döngü ya da tekrar
        for (String child : children.getOrDefault(cur, List.of())) stack.push(child);
    }
    visited.remove(root);
    return visited;
}

BFS'te düğümü kuyruğa eklerken işaretlemek, aynı düğümün kuyruğa defalarca girmesini önler. DFS'i özyinelemeli yazmak kısa ama derin ağaçta StackOverflowError riski taşır; iteratif versiyon bunu önler. Karmaşıklık: O(V + E); ızgarada O(satır × sütun).

Binary search. Sıralı veride O(log n). En sık hata sınırlardır; yarı açık aralık [lo, hi) ile "hedefe eşit ya da büyük ilk indeks" (lower bound) şablonu çoğu varyasyonu çözer:

static int lowerBound(long[] sorted, long target) {
    int lo = 0, hi = sorted.length;                                 // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;                               // (lo + hi) / 2 int taşabilir
        if (sorted[mid] < target) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Daha güçlü varyasyon cevap üzerinde binary search'tür: "Siparişler sırayla, en fazla 5 günde kargolanacak; günlük minimum kapasite ne olmalı?" Kapasite arttıkça gereken gün sayısı azalır (monoton), bu yüzden kapasite aralığında (max(ağırlık)..toplam) binary search yapılır ve her adımda O(n) bir kontrol çalışır: O(n log toplam).

Dengeli parantez. Açılanı stack'e at, kapanışta tepedekiyle eşleşiyor mu bak; sonunda stack boş olmalı:

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(', '[', '{' -> stack.push(c);
            case ')', ']', '}' -> {
                if (stack.isEmpty()) return false;                  // ")(" gibi
                char open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
            }
            default -> { }
        }
    }
    return stack.isEmpty();                                         // "((" gibi
}

Anagram gruplama. Her kelimenin bir imzası olur (harfleri sıralanmış hali); aynı imzalılar aynı gruba girer:

static Collection<List<String>> groupAnagrams(List<String> words) {
    Map<String, List<String>> groups = new LinkedHashMap<>();
    for (String w : words) {
        char[] chars = w.toCharArray();
        Arrays.sort(chars);
        groups.computeIfAbsent(new String(chars), key -> new ArrayList<>()).add(w);
    }
    return groups.values();
}

Karmaşıklık O(n × L log L) (L kelime uzunluğu). Alfabe küçük ve sabitse imza 26 elemanlı bir sayaç dizisinden üretilerek O(n × L)'ye iner. Bu kalıp genelleşir: "eşdeğer olanları grupla" sorularında bir kanonik anahtar üret, computeIfAbsent ile topla.

Quiz'deki sorular: çözüm ve nedenleri

k7: Kullanıcı başına rate limiter

Görev: boolean tryAcquire(String userId); dakikada en fazla 5 istek; thread-safe; zaman kaynağı test edilebilir; test; bellek ve çok pod'lu durumun tartışması.

Doğru çözüm: Token bucket (ya da sliding window), ConcurrentHashMap<String, Bucket> + computeIfAbsent, kova güncellemesi kullanıcı başına synchronized (ya da GCRA ile tek AtomicLong + CAS), LongSupplier/Clock enjeksiyonu ve sahte saatle test, Caffeine expireAfterAccess ile bellek, Redis + Lua ile dağıtık limit, 429 + Retry-After.

Sık yapılan yanlış yaklaşımlar ve neden yanlış oldukları:

• HashMap + kilitsiz güncelleme: HashMap eşzamanlı yazmada bozulur; sayaç güncellemesi de yarışa açıktır.
• ConcurrentHashMap var, kova güncellemesi kilitsiz: Map'in thread-safe olması bileşik "oku-hesapla-yaz" işlemini atomik yapmaz; aynı kullanıcıdan eşzamanlı istekler limiti aşar.
• Tüm metodu synchronized yapmak: Doğrudur ama tüm kullanıcılar tek kilide bağlanır; yükte gereksiz contention. Kullanıcı başına kilit yeterlidir.
• Her kullanıcı için zamanlayıcıyla token eklemek: Milyonlarca kullanıcıda milyonlarca zamanlanmış görev; lazy refill aynı sonucu sıfır maliyetle verir.
• System.currentTimeMillis() doğrudan: Test için Thread.sleep gerekir; duvar saati geri de gidebilir.
• Dağıtıkta "GET, hesapla, SET": İki pod aynı anda okur; atomiklik için Lua script ya da tek komutluk algoritma gerekir.

Kata çözümüne not: Kata, token'ı double ve "nano başına token" oranıyla tutuyor. Verilen test (5 token, 60 saniye) geçiyor; ancak 1-1000 arası kapasite ve 1/7/60/3600 saniyelik periyotlarla (periyodun kapasiteye tam bölündüğü durumlar) yapılan denemede, tam bir token süresi geçtiğinde biriken değerin 20 kombinasyonda 1.0'ın altında kaldığı ve token'ın bir istek geç verildiği görüldü. Yukarıdaki tamsayı (token başına nanosaniye) versiyon ya da GCRA bu hatayı ortadan kaldırır.

Production karşılığı: Rate limiting çoğu zaman uygulama kodunda değil, API gateway'de (Spring Cloud Gateway RedisRateLimiter, Envoy, Nginx) yapılır; uygulama seviyesindeki limit iş kuralına özgü olanlar içindir (kullanıcı başına kupon denemesi). Limit anahtarı IP olursa NAT ve mobil operatörlerin arkasındaki binlerce meşru kullanıcı tek IP'yi paylaşır; kimliği doğrulanmış kullanıcı ya da API key daha adildir.

k8: LRU cache

Görev: get(K) → Optional<V>, put(K, V), kapasite; get de kullanım sayılır; thread-safety tartışması; "LinkedHashMap olmadan" varyasyonu.

Doğru çözüm: Önce LinkedHashMap(16, 0.75f, true) + removeEldestEntry söylenir ve yazılır; istenirse HashMap<K, Node> + sentinel'lı çift yönlü liste. Her iki işlem O(1). Thread-safety için synchronized metotlar; production'da Caffeine.

Sık yapılan yanlış yaklaşımlar:

• accessOrder parametresini vermemek: Varsayılan ekleme sırasıdır; sonuç LRU değil FIFO olur, get sırayı güncellemez.
• ArrayList/LinkedList + remove(Object) ile en yeniye taşımak: Listede arama O(n); O(1) şartı bozulur.
• Node'da key'i tutmamak: Listenin sonundan silinen node'un map'ten de silinmesi için key gerekir; aksi halde map'te O(n) arama ya da sızıntı.
• put ile var olan anahtarı güncellerken sırayı güncellememek: Güncellenen değer hâlâ "en eski" sayılır ve ilk atılan o olur.
• ReadWriteLock ile okumaları paralel yapmak: accessOrder modunda get iç listeyi değiştirir; paralel get'ler listeyi bozar.
• Kapasite kontrolünü eklemeden önce >= ile yapmak ya da hiç yapmamak: Off-by-one ile kapasite bir eksik ya da bir fazla olur; kapasite 1 testi bunu yakalar.

Production karşılığı: Pod başına in-memory cache'lerde asıl problem algoritma değil tutarlılıktır: 20 pod'da ürün fiyatı değişince 20 ayrı cache bayat kalır. Çözümler: kısa TTL, değişiklik event'iyle (Kafka) invalidation, ya da paylaşılan Redis cache. Cache isabet oranını (Caffeine recordStats()) metrik olarak izlemek, kapasitenin doğru seçilip seçilmediğini söyler.

k9: Kampanya dönemlerini birleştir

Görev: Çakışan ve ardışık dönemleri birleştir; sonuç başlangıca göre sıralı ve çakışmasız; boş, tek, iç içe ve ardışık durumlar; karmaşıklık.

Doğru çözüm: Kopyayı başlangıca göre sırala; tek geçişte next.start <= current.end + 1 gün ise end = max(current.end, next.end), değilse current'ı sonuca ekle. O(n log n) zaman, O(n) bellek.

Sık yapılan yanlış yaklaşımlar:

• Sıralamadan birleştirmeye çalışmak: Sırasız listede tek geçiş, sonradan gelen ve önceki iki dönemi köprüleyen dönemi kaçırır.
• end = next.end (max almamak): İç içe dönemde (1-10, 2-3) sonuç 1-3'e küçülür.
• Bitişikliği < ile kontrol etmek: 1-3 ve 4-6 birleşmez; iş kuralı ihlali. Ya da tersi: saat bazlı yarı açık aralıklarda +1 eklemek bitişik olmayanları birleştirir.
• Girdiyi yerinde sıralamak: Çağıranın listesi değişir; immutable listede UnsupportedOperationException.
• Son current'ı sonuca eklemeyi unutmak: Döngü bitince son birleşik dönem kaybolur; tek elemanlı liste testinde boş sonuç döner.

Production karşılığı: Aynı mantık rezervasyon çakışma kontrolü ve teslimat penceresi hesaplarında kullanılır. PostgreSQL'de aralık tipleri (daterange) ve EXCLUDE USING gist (... WITH &&) constraint'i, çakışan aralıkların eklenmesini veritabanı seviyesinde engelleyebilir. Sürekli eklenen çok sayıda aralıkta her seferinde yeniden sıralamak yerine TreeMap<LocalDate, Period> ile floorEntry/ceilingEntry kullanarak amortize O(log n) ekleme yapılır.

k10: En çok satan K ürün

Görev: Satırlardan ürün başına toplam adet; adede göre azalan, eşitlikte küçük id önce; ilk K; karmaşıklık ve heap/sıralama karşılaştırması; kenar durumları.

Doğru çözüm: HashMap.merge ile toplam (O(n)); boyutu K olan min-heap (O(m log k)) ya da m küçükse sıralama (O(m log m)); heap'ten çıkan sıra kötüden iyiye olduğu için sonuç ters çevrilir.

Sık yapılan yanlış yaklaşımlar:

• Max-heap'e her şeyi koyup K kez poll: Doğru sonuç verir ama tek tek offer ile O(m log m) (toplu heapify ile O(m + k log m)) zaman ve O(m) bellek; "boyutu K heap" avantajını kaçırır. (Kötü değil, ama karşılaştırmayı söylemek gerekir.)
• Min-heap'te eşitlik comparator'ını ters kurmak: Eşit adetli ürünlerden yanlış olan (küçük id) atılır.
• Heap'ten çıkanı ters çevirmemek: Sonuç artan sırada gelir.
• Toplamı int'te tutmak: Büyük günlerde taşma.
• k <= 0 ya da k > m kontrolü yok: Boş heap'te poll ile null, ya da gereksiz exception.
• PriorityQueue'yu iterasyonla okumak: Heap'in iç dizisi sıralı değildir; çıktı rastgele görünür.

Production karşılığı: Takip sorusu "1000 pod'dan top-K'yı nasıl birleştirirsin, her pod'un top-K'sı yetmez mi?" Yetmez: bir ürün her pod'da 11. sırada olup toplamda 1. olabilir. Kesin sonuç için sayımlar ürün id'sine göre partition'lanıp (Kafka key = productId) her partition'da tam sayım yapılır, sonra partition başına top-K'lar birleştirilir. Ya da tek bir Redis Sorted Set'e ZINCRBY.

Üç seviyede cevap

Soru: "Dağıtık bir rate limiter nasıl tasarlarsın?"

Soru: "Thread-safe bir LRU cache yazar mısın? Production'da da bunu mu kullanırsın?"

Soru: "HashMap'in get ve put'u neden O(1)? Her zaman O(1) mi?"

Soru: "Günün en çok satan 10 ürününü bul. Veri milyonlarca satırsa ne değişir?"

Sorulmadı ama sorulabilir

LFU cache

LFU (Least Frequently Used), en az sayıda kullanılanı atar; eşitlikte en eskiyi. O(1) tasarım: key → değer, key → frekans ve frekans → erişim sıralı key kümesi (LinkedHashSet) map'leri ile o anki minimum frekans. Erişimde anahtar bir üst frekans kümesine taşınır; minimum frekans kümesi boşaldıysa minFreq artar; yeni anahtar her zaman frekans 1 ile girer ve minFreq = 1 olur.

public final class LfuCache<K, V> {
    private final int capacity;
    private final Map<K, V> values = new HashMap<>();
    private final Map<K, Integer> freqs = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>();
    private int minFreq;

    public LfuCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
    }

    public Optional<V> get(K key) {
        if (!values.containsKey(key)) return Optional.empty();
        touch(key);
        return Optional.of(values.get(key));
    }

    public void put(K key, V value) {
        if (values.containsKey(key)) { values.put(key, value); touch(key); return; }
        if (values.size() == capacity) {
            K victim = byFreq.get(minFreq).iterator().next();      // en düşük frekans, en eski
            byFreq.get(minFreq).remove(victim);
            values.remove(victim);
            freqs.remove(victim);
        }
        values.put(key, value);
        freqs.put(key, 1);
        byFreq.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void touch(K key) {
        int f = freqs.get(key);
        LinkedHashSet<K> set = byFreq.get(f);
        set.remove(key);
        if (set.isEmpty() && f == minFreq) minFreq++;
        freqs.put(key, f + 1);
        byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
    }
}

LFU'nun zayıflığı: geçmişte çok popüler olmuş ama artık kullanılmayan anahtar yüksek frekansıyla cache'te kalır (frekans yaşlandırma gerekir). LRU'nun zayıflığı: tek seferlik büyük bir tarama sıcak veriyi siler. Caffeine'in W-TinyLFU'su ikisini birleştirir: küçük bir LRU penceresi ve yaşlanan, yaklaşık bir frekans taslağı ile "kabul" kararı.

Tek cümle: "Erişim deseni kalıcı popülerliğe dayanıyorsa LFU, yakınlığa dayanıyorsa LRU; production'da ikisinin avantajını birleştiren Caffeine'i kullanırım."

Consistent hashing

N cache node'una anahtar dağıtırken hash(key) % N kullanırsan, N değiştiğinde anahtarların büyük çoğunluğu başka node'a taşınır: 4'ten 5 node'a geçişte 100.000 anahtarlık denemede yaklaşık 80.000'i yer değiştirdi; bu bir cache için toplu miss ve veritabanına yük dalgası demektir. Consistent hashing'de node'lar ve anahtarlar aynı hash halkasına yerleşir; anahtar saat yönünde ilk node'a gider. Yeni node sadece halkadaki komşusunun anahtarlarının bir kısmını alır: aynı denemede yaklaşık 21.000 anahtar (~1/5) taşındı ve hepsi yeni node'a gitti. Her fiziksel node'u halkaya çok sayıda sanal node olarak koymak dağılımı dengeler.

final class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int virtualNodes;

    ConsistentHashRing(int virtualNodes) { this.virtualNodes = virtualNodes; }

    void addNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.put(hash(node + "#" + i), node);
    }

    void removeNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.remove(hash(node + "#" + i));
    }

    String nodeFor(String key) {
        if (ring.isEmpty()) throw new IllegalStateException("no nodes");
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));     // saat yönünde ilk node
        return (e != null ? e : ring.firstEntry()).getValue();        // halkanın sonu: başa sar
    }

    private static long hash(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }
}

String.hashCode() burada uygun değildir: dağılımı zayıftır ve benzer anahtarlar halkada kümelenir. MD5 burada güvenlik için değil dağılım için kullanılıyor; production'da MurmurHash gibi hızlı, kriptografik olmayan bir hash tercih edilir. Kullanıldığı yerler: Cassandra/DynamoDB partition dağılımı, istemci taraflı cache sharding, sticky load balancing. Redis Cluster ise farklı bir yol izler: 16384 sabit hash slot ve slot'ların node'lara atanması.

Tek cümle: "hash % N node sayısı değişince neredeyse her şeyi taşır; consistent hashing sadece ~1/N'ini taşır, sanal node'lar da yükü dengeler."

Sliding window counter (yaklaşık sayaç)

Sliding window log'un kesinliğini kullanıcı başına iki sayaçla yaklaşık olarak elde eder: tahmini sayı = şimdiki pencere sayacı + önceki pencere sayacı × (önceki pencerenin hâlâ kayan pencereye düşen oranı). Dakikanın 15. saniyesindeysen önceki dakikanın %75'i sayılır. Fixed window'un sınır patlamasını büyük ölçüde giderir, bellek kullanıcı başına iki sayıdır. İsteklerin önceki pencerede düzgün dağıldığı varsayımına dayandığı için yaklaşıktır.

Tek cümle: "Kesinlik gerekmeyen, çok kullanıcılı limitlerde sliding window counter iki sayaçla sliding log'a çok yakın sonuç verir."

Stream'de kayan pencere top-K

"Son 1 saatin en çok satanları": Saatlik değil dakikalık sayaçlar tutulur (ör. Redis'te dakika başına bir Sorted Set, 61 dakika TTL), sorguda son 60 dakikanın set'leri ZUNIONSTORE ile birleştirilip ilk K okunur. Birleştirme maliyetini azaltmak için sonuç birkaç saniye cache'lenir. Kafka Streams'te aynı problem hopping window + aggregation ile çözülür.

Tek cümle: "Kayan pencere top-K'yı küçük sabit pencerelerin (dakikalık kova) toplamı olarak modellerim; kesinlik/tazelik dengesini kova boyutu belirler."

Cevap üzerinde binary search

Sorunun cevabı monoton bir koşula bağlıysa ("kapasite arttıkça gereken gün azalır"), cevap aralığında binary search yapılır ve her adımda koşul O(n)'de kontrol edilir:

static int minDailyCapacity(int[] weights, int days) {
    int lo = Arrays.stream(weights).max().orElseThrow();            // en ağır paket sığmalı
    int hi = Arrays.stream(weights).sum();                          // hepsi tek günde
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (daysNeeded(weights, mid) <= days) hi = mid; else lo = mid + 1;
    }
    return lo;
}

private static int daysNeeded(int[] weights, int capacity) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > capacity) { days++; load = 0; }
        load += w;
    }
    return days;
}

{1..10} ağırlıkları ve 5 gün için sonuç 15'tir. Aynı kalıp: "SLA'yı sağlayan minimum pod sayısı", "bütçeye sığan maksimum batch boyutu".

Tek cümle: "Cevap monoton bir koşula bağlıysa cevabın kendisi üzerinde binary search yaparım: O(n log aralık)."

Sık yapılan hatalar

• Netleştirmeden kodlamaya başlamak → Yanlış problemi çözersin (ardışık dönemler, eşitlik kuralı) → Önce gereksinimi tekrar et, kenar durumları sor.
• Karmaşıklığı söylememek ya da sadece zamanı söylemek → Mülakatçı trade-off düşünüp düşünmediğini göremez → Zaman ve bellek, ortalama ve en kötü durum.
• ConcurrentHashMap var diye bileşik işlemi atomik sanmak → Oku-hesapla-yaz yarışı, limit aşılır → Kullanıcı başına kilit, compute, ya da CAS.
• Zamanı doğrudan System.currentTimeMillis() ile almak → Test için sleep, duvar saati geri gidebilir → LongSupplier/Clock enjekte et, süre için monoton saat.
• Rate limiter map'inin sınırsız büyümesi → Bellek sızıntısı → TTL'li cache (Caffeine) ya da Redis PEXPIRE.
• Dağıtık limitte GET + SET → Pod'lar arası yarış → Tek Lua script; INCR ve EXPIRE aynı atomik birimde.
• LRU'da accessOrder unutmak → FIFO cache → new LinkedHashMap<>(16, 0.75f, true).
• ReadWriteLock ile LRU okuması → get yazmadır, liste bozulur → Tek kilit ya da Caffeine.
• Merge intervals'ta max almamak → İç içe aralık küçülür → end = max(current.end, next.end).
• Girdiyi yerinde sıralamak → Çağıranın verisi değişir, immutable listede exception → new ArrayList<>(input).
• Top-K min-heap'te comparator'ı ters kurmak → Yanlış eleman atılır → "Tepede atılacak olan durur" kuralıyla yaz, eşitliği örnekle test et.
• PriorityQueue'yu iterasyonla sıralı sanmak → Rastgele görünen çıktı → poll ile boşalt.
• (lo + hi) / 2 → Büyük indekslerde int taşması → lo + (hi - lo) / 2.
• BFS'te düğümü kuyruktan çıkarırken işaretlemek → Aynı düğüm kuyruğa defalarca girer → Eklerken işaretle.
• Özyinelemeli DFS'i derin veride kullanmak → StackOverflowError → İteratif DFS (ArrayDeque).
• Stack için java.util.Stack → Her metodu senkronize, eski API → ArrayDeque.

Hızlı tekrar

Kaynaklar

• Java SE 21 API: PriorityQueue: Heap işlemlerinin karmaşıklıklarının resmi tanımı.
• Java SE 21 API: LinkedHashMap: accessOrder ve removeEldestEntry ile LRU kurulumu; erişim sıralı modda get'in yapısal değişiklik olduğu notu.
• Java SE 21 API: HashMap: Load factor, kapasite ve iterasyon maliyeti.
• Redis: Scripting with Lua: Script atomikliği ve anahtarların neden KEYS ile verilmesi gerektiği.
• Stripe: Scaling your API with rate limiters: Token bucket ve farklı limiter türlerinin production'da birlikte kullanımı.
• Cloudflare: How we built rate limiting capable of scaling to millions of domains: Sliding window counter yaklaşımı ve doğruluğu.
• Caffeine: Efficiency: W-TinyLFU'nun LRU ve LFU ile karşılaştırması.
• Joshua Bloch, Effective Java (3. baskı), Madde 10-11: equals ve hashCode sözleşmesi; hash tabanlı koleksiyonların neden buna bağlı olduğu.