Akan veride medyan

Problem

Sayıların tek tek geldiği bir yapı tasarla. İki işlem var:

• addNum(num): yeni bir tamsayıyı yapıya ekler.
• findMedian(): şimdiye kadar eklenen tüm sayıların medyanını döndürür. Eleman sayısı tekse sıralı halin ortasındaki eleman, çiftse ortadaki iki elemanın ortalaması (ondalıklı olabilir).

Her iki işlem de çok sık çağrılacak; özellikle findMedian hızlı olmalı.

addNum(6)    findMedian() -> 6.0
addNum(2)    findMedian() -> 4.0     (2, 6)
addNum(9)    findMedian() -> 6.0     (2, 6, 9)
addNum(1)    findMedian() -> 4.0     (1, 2, 6, 9)

Netleştirme soruları

• Hiç eleman yokken findMedian çağrılırsa ne olmalı? (Exception, NaN, Optional?)
• addNum ve findMedian oranı ne? (Okuma ağırlıklıysa ekleme biraz pahalı olabilir.)
• Değer aralığı? Değerler küçük bir aralıkta mı (ör. 0-100)? (Sayaç dizisiyle çok daha basit çözüm.)
• İki büyük int'in ortalaması taşar mı? (Integer.MAX_VALUE iki kez gelirse.)
• Thread-safe olmalı mı? Elemanlar silinebilir mi (kayan pencere)?

İpuçları

Yaklaşım

Brute force 1, her sorguda sırala: addNum O(1) (listeye ekle), findMedian O(n log n). Sorgular sıksa çok yavaş.

Brute force 2, sıralı liste: addNum'da binary search ile yeri bul ve araya ekle; findMedian O(1). Ama ArrayList'e araya ekleme kaydırma gerektirir: O(n). n ekleme için O(n²) toplam. Küçük n'de pratikte fena değil (System.arraycopy hızlıdır), ama asimptotik olarak yetersiz.

Optimal, iki heap: Veriyi iki yarıya böl:

• lower: küçük yarı, max-heap (tepesi küçük yarının en büyüğü).
• upper: büyük yarı, min-heap (tepesi büyük yarının en küçüğü).

Değişmezler: (1) lower'daki her eleman upper'dakilerden küçük ya da eşit; (2) lower.size() == upper.size() ya da lower.size() == upper.size() + 1.

Bu durumda medyan: boyutlar farklıysa lower'ın tepesi, eşitse iki tepenin ortalaması. O(1).

addNum üç adım:

1. Sayıyı lower'a ekle.
2. lower'ın en büyüğünü upper'a taşı. Bu adım değişmez (1)'i garanti eder: yeni sayı hangi yarıya ait olursa olsun, sınırdaki eleman doğru tarafa geçer.
3. upper artık daha büyükse en küçüğünü lower'a geri taşı. Bu adım değişmez (2)'yi garanti eder.

Her addNum sabit sayıda (en fazla 5) heap işlemi yapar: O(log n). "Hangi heap'e eklemeliyim?" diye karşılaştırma dalları yazmak da mümkündür, ama bu "her zaman aynı yoldan geç" versiyonu, dal hatalarını ortadan kaldırdığı için mülakatta daha güvenlidir.

Java'da max-heap new PriorityQueue<>(Collections.reverseOrder()) ile kurulur. Ortalama için ((long) a + b) / 2.0: iki büyük int'in toplamı int'te taşar; testte Integer.MAX_VALUE iki kez eklenerek denendi.

Java çözümü

import java.util.Collections;
import java.util.PriorityQueue;

public final class MedianFinder {

    // lower: küçük yarı (max-heap), upper: büyük yarı (min-heap)
    // Değişmezler: max(lower) <= min(upper) ve lower.size() == upper.size() veya bir fazlası
    private final PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> upper = new PriorityQueue<>();

    public void addNum(int num) {
        lower.offer(num);
        upper.offer(lower.poll());                                 // küçük yarının en büyüğü büyük yarıya geçer
        if (upper.size() > lower.size()) {
            lower.offer(upper.poll());                             // boyut dengesini geri kur
        }
    }

    public double findMedian() {
        if (lower.isEmpty()) {
            throw new IllegalStateException("no numbers added yet");
        }
        if (lower.size() > upper.size()) {
            return lower.peek();
        }
        return ((long) lower.peek() + upper.peek()) / 2.0;         // long: iki büyük int toplamı taşmasın
    }
}

Karmaşıklık

• addNum: O(log n); sabit sayıda heap işlemi.
• findMedian: O(1); iki peek.
• Bellek: O(n); her eleman tam olarak bir heap'te durur.
• Değer aralığı küçükse (ör. 0-100) 101 elemanlı bir sayaç dizisi ile addNum O(1), findMedian O(101) olur; takip sorusu olarak çok sorulur.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 500 rastgele senaryoda (her biri 1-40 ekleme, değerler -20..20) her eklemeden sonra medyan, listeyi sıralayan referansla karşılaştırıldı.

Negatif örnek önemli bir tuzağı gösterir: (a + b) / 2 tamsayı bölmesiyle yazılırsa -3 / 2 = -1 olur ve sonuç -1.0 çıkar; 2.0 ile bölmek gerekir.

Mülakatçı için

Bu soru bir veri yapısı tasarımı sorusudur: adayın değişmez (invariant) tanımlayıp her işlemde koruyabilmesi ölçülür. İki heap fikrini bilen çok aday var; ayrım, değişmezleri açıkça söyleyip söylemediği ve addNum'un neden değişmezleri koruduğunu açıklayabilmesidir. Max-heap'i Java'da nasıl kuracağını bilmemek küçük ama gerçek bir eksiktir.

İpucu zamanlaması: Aday sıralı listeyle başlarsa kabul et, ekleme maliyetini sor. 10 dakika içinde iki heap fikri gelmezse ikinci ipucunu ver. Dengeleme kodunda dallar karışıyorsa "her sayıyı önce bir heap'ten geçirip diğerine aktarsan?" diye öner. Ortalamada tamsayı bölmesi yaparsa -1, -2 örneğini ver.

Takip soruları:

1. Değerlerin %99'u 0-100 arasında; buna göre optimize et. (Beklenen: 0-100 için sayaç dizisi, aralık dışı için iki küçük heap ya da sıralı yapı; medyan neredeyse her zaman sayaçtan bulunur.)
2. Son k elemanın medyanı (kayan pencere). (Beklenen: silme gerekir; iki heap + lazy deletion (silinecekleri map'te say, tepeye geldiğinde at) ya da iki TreeMap; LeetCode 480.)
3. Bu bir gecikme izleme servisi; 50. değil 99. yüzdelik (p99) gerekiyor ve veri milyarlarca ölçüm. (Beklenen: kesin hesap pahalı; HdrHistogram, t-digest ya da DDSketch gibi yaklaşık yapılar; Micrometer/Prometheus'ta histogram kovaları ve quantile hesaplamanın birleştirilebilirlik sorunu.)

Benzer problemler

• Sliding Window Median (LeetCode 480).
• IPO (LeetCode 502): iki heap ile açgözlü seçim.
• Kth Largest Element in a Stream (LeetCode 703): boyutu k min-heap.
• Top K Frequent Elements (LeetCode 347) (bu sette: top-k-frequent-elements).
• Sliding Window Maximum (LeetCode 239) (bu sette: sliding-window-maximum).