Zaman damgalı anahtar-değer deposu

Problem

Her anahtar için değerin geçmişini saklayan bir depo tasarla. İki işlem var:

• set(key, value, timestamp): anahtarın bu zaman damgasındaki değerini kaydeder.
• get(key, timestamp): anahtar için, zaman damgası verilen değerden küçük ya da eşit olan kayıtlar içinden en geç olanın değerini döndürür. Böyle bir kayıt yoksa boş string döner.

Aynı anahtar için set çağrılarının zaman damgaları kesin artan sırada gelir.

set("kur", "32.10", 10)
set("kur", "32.45", 20)
get("kur", 5)   -> ""        (10'dan önce kayıt yok)
get("kur", 15)  -> "32.10"
get("kur", 25)  -> "32.45"
get("yok", 10)  -> ""

Netleştirme soruları

• Zaman damgaları anahtar başına artan sırada mı garanti? (Bu, sıralı ekleme ve binary search'ün temeli.)
• Aynı zaman damgasıyla iki set gelirse? (Garanti dışı; gelirse son yazan mı kazanmalı?)
• get ve set oranı ne? Hangisi daha sık? (Veri yapısı seçimini etkiler.)
• Thread-safe olmalı mı?
• Eski versiyonlar silinebilir mi (retention), yoksa sonsuza kadar mı tutulacak?

İpuçları

Yaklaşım

Brute force: Her anahtar için listeyi sondan başa tara, timestamp <= t olan ilk kaydı döndür. set O(1), get O(m) (m: anahtarın versiyon sayısı). Yazma ağırlıklı ve az versiyonlu bir iş yükünde bu yeterli bile olabilir; mülakatta söylemeye değer.

Optimal, HashMap + sıralı liste + binary search: Problemin garantisi sayesinde her anahtarın listesi set ile sona ekleyerek sıralı kalır, set amortize O(1). get'te upper bound: [lo, hi) yarı açık aralıkla timestamp <= t olanları sola at; döngü bitince lo, t'den büyük ilk index'tir. Cevap lo - 1; lo == 0 ise hiç uygun kayıt yoktur.

Alternatif, TreeMap<Integer, String>: Her anahtar için bir TreeMap tut, get için floorEntry(t) kullan. Hem set hem get O(log m) ve sıralı gelme garantisine ihtiyaç duymaz; damgalar karışık sırada gelse de çalışır. Bedeli: girdi başına daha fazla nesne ve bellek (kırmızı-siyah ağaç düğümleri). Mülakatta en temiz cevap genelde şu: "Garanti varsa liste + binary search; yoksa TreeMap."

Versiyon değerini record Version(int timestamp, String value) ile modellemek, paralel iki liste tutmaktan (List<Integer> + List<String>) daha okunaklıdır; paralel listelerin senkron kalmaması klasik bir hata kaynağıdır.

Java çözümü

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public final class TimeMap {

    private record Version(int timestamp, String value) { }

    private final Map<String, List<Version>> versionsByKey = new HashMap<>();

    // Varsayım (problemin garantisi): aynı key için timestamp'ler artan sırada gelir
    public void set(String key, String value, int timestamp) {
        versionsByKey.computeIfAbsent(key, k -> new ArrayList<>()).add(new Version(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<Version> versions = versionsByKey.get(key);
        if (versions == null) {
            return "";
        }
        // timestamp'i timestamp'ten BÜYÜK olan ilk versiyonu bul; cevap onun bir solu
        int lo = 0, hi = versions.size();                          // yarı açık [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (versions.get(mid).timestamp() <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo == 0 ? "" : versions.get(lo - 1).value();
    }
}

Kendi binary search'ünü yazmak yerine Collections.binarySearch da kullanılabilir, ama tam eşleşme yoksa -(insertionPoint) - 1 döndürdüğü için dönüşüm hatası yapmak kolaydır; mülakatta elle yazılan net bir upper bound daha güvenlidir.

Karmaşıklık

• set: amortize O(1) (map erişimi + listeye ekleme). TreeMap versiyonunda O(log m).
• get: O(log m); map erişimi O(1) ortalama + binary search.
• Bellek: O(toplam set sayısı).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 300 rastgele senaryoda (her biri 60 karışık set/get, 3 anahtar) her anahtar için TreeMap.floorEntry kullanan referans uygulamayla karşılaştırıldı.

Son satır bir tasarım uyarısıdır: boş string hem "değer boş" hem "kayıt yok" anlamına geliyor. Gerçek bir API'de Optional<String> döndürmek bu belirsizliği kaldırır.

Mülakatçı için

Bu soru bir veri yapısı tasarımı + binary search karışımıdır ve backend dünyasına çok yakındır: MVCC (PostgreSQL'in satır versiyonları), event sourcing'de "t anındaki durum", konfigürasyon geçmişi, döviz kuru geçmişi. Güçlü aday, problemin "artan damga" garantisinin neden önemli olduğunu ve garanti olmasaydı ne değişeceğini kendiliğinden söyler.

İpucu zamanlaması: Aday get'te lineer tarama yaparsa kabul et ve "her anahtar için milyonlarca versiyon olursa?" diye sor. Upper bound'da sınır hatası yaparsa (lo - 1 yerine lo) "tam damga" ve "arada" örneklerini yürütmesini iste. TreeMap ile başlarsa çok iyi; garanti varken listenin neden daha hafif olduğunu sor.

Takip soruları:

1. Bu yapıyı thread-safe yap; okumalar yazmalardan 100 kat fazla. (Beklenen: ConcurrentHashMap + anahtar başına kilit ya da ConcurrentSkipListMap; copy-on-write liste okuma ağırlıklı yükte uygun ama yazma maliyeti O(m).)
2. Bellek sınırsız büyüyor; 30 günden eski versiyonları sil. (Beklenen: anahtar başına baştan kırpma, TreeMap'te headMap(t).clear(); arka planda periyodik temizlik ya da yazma sırasında lazy temizlik.)
3. Bunu bir veritabanında modellesen? (Beklenen: (key, ts) birleşik index ve WHERE key = ? AND ts <= ? ORDER BY ts DESC LIMIT 1; index sayesinde aynı floor araması.)

Benzer problemler

• Snapshot Array (LeetCode 1146): aynı versiyonlama fikri, index bazlı.
• Stock Price Fluctuation (LeetCode 2034): veri yapısı tasarımı + sıralı yapı.
• LRU Cache (LeetCode 146): klasik veri yapısı tasarımı.
• Koko Eating Bananas (LeetCode 875): binary search sınır disiplini (bu sette: koko-eating-bananas).