Live coding · Algoritma · HashMap · Heap

En çok satan K ürün

OrtaHedef 15 dk

Klasik (top-K), e-ticaret senaryosuyla

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

Kampanya panosu, günün sipariş satırlarından toplam adede göre en çok satan K ürünü gösterecek. Eşit adette küçük productId önce gelsin. Bir ürün birden fazla satırda geçebilir.

Görevler

  1. List<Long> topK(List<OrderLine> lines, int k) yaz (azalan sırada).
  2. Karmaşıklığı söyle ve sıralama ile heap yaklaşımını karşılaştır.
  3. Kenar durumları: k ≤ 0, k > farklı ürün sayısı, eşitlik.
Başlangıç kodu
record OrderLine(long productId, int quantity) {}

static List<Long> topK(List<OrderLine> lines, int k) {
    return List.of();
}

// Örnek: [(1,5), (2,3), (3,5), (2,4), (4,1), (5,7)], k = 3
// toplamlar: 1→5, 2→7, 3→5, 4→1, 5→7
// → [2, 5, 1]   (2 ve 5 eşit: küçük id önce; 1 ve 3 eşit: 1 önce)
İpucu 1

Önce ürün başına toplam: HashMap.merge(productId, qty, Long::sum).

İpucu 2

Basit yol: entry'leri sırala ve ilk k'yı al, O(m log m). Daha iyi yol: boyutu k olan min-heap, O(m log k).

İpucu 3

Min-heap'te tepede 'en kötü' eleman durmalı: değeri küçük olan, eşitlikte id'si BÜYÜK olan. Sonunda heap'i boşaltıp ters çevir.

Referans çözümü göster
Çözüm
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);   // O(n)
    }

    // Min-heap: tepede "en kötü" aday durur. Adet küçükse ya da eşitlikte id büyükse daha kötü.
    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()) {                        // O(m log k)
        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;
}

// Stream alternatifi (m küçükse yeterli, O(m log m)):
// return totals.entrySet().stream()
//         .sorted(Map.Entry.<Long, Long>comparingByValue().reversed().thenComparing(Map.Entry.comparingByKey()))
//         .limit(k).map(Map.Entry::getKey).toList();
// Örnekle test edildi: [2, 5, 1].
Açıklama: neden böyle?
  • Heap neden? m farklı ürün varsa tam sıralama O(m log m) sürer. Boyutu k olan min-heap O(m log k) sürer ve sadece O(k) ek bellek kullanır. k=10, m=1 milyon için ciddi bir fark.
  • Comparator'ı doğru kurmak bu sorunun en çok hata yapılan yeri. Önce kafanda "heap'in tepesinde kim durmalı?" sorusunu cevapla, sonra comparator'ı yaz.
  • Gerçek sistemde: Gün boyunca akan event'ler için Kafka Streams / Flink ile pencereli sayım, ya da Redis Sorted Set (ZINCRBY + ZREVRANGE 0 k-1). Bu cevap system design'a köprü kurar.
  • Yaklaşık çözüm: Count-Min Sketch + heap. Çok büyük veride kesinliği bellekle takas eder. Bunu bilmek bonus.
  • Ürün başına toplam: HashMap merge / groupingBy summing
  • Seçim: boyutu k olan min-heap (PriorityQueue) ya da sıralama + limit
  • Eşitlik kuralı: aynı adette küçük id önce (thenComparing)
  • Doğru sıra: azalan sonuç (heap'ten çıkan listeyi ters çevirme)
  • Karmaşıklık: O(n + m log k) ile O(m log m) karşılaştırması
  • Kenar durumları: k ≤ 0, k > farklı ürün
  • Siparişler canlı bir stream olarak gelse ve son 1 saatin top-10'u istense? (sliding window, Redis ZSET)
  • Kategori başına top-K istense? (Map<kategori, heap> ya da SQL'de window function)
  • Bu sonucu 1000 pod'dan birleştirmen gerekse? (her pod'un top-K'sı yetmez, neden?)