En sık geçen K kelime

Problem

Bir kelime dizisi ve bir k değeri veriliyor. En sık geçen k kelimeyi, sıklığa göre çoktan aza sıralı bir liste olarak döndür. İki kelimenin sıklığı eşitse sözlük sırasında önce gelen (alfabetik olarak küçük olan) önce yer alır. Hedef, tüm kelimeleri sıralamaktan daha iyi, O(n log k) bir çözüm.

Girdi:  words = ["kalem", "defter", "kalem", "silgi", "defter", "kalem", "cetvel"], k = 2
Çıktı:  ["kalem", "defter"]           (kalem: 3, defter: 2)

Girdi:  words = ["elma", "armut", "kiraz", "armut", "elma", "kiraz", "muz"], k = 2
Çıktı:  ["armut", "elma"]             (üçü de 2 kez; sözlük sırasıyla ilk ikisi)

Goldman Sachs online assessment'ında bir aday bu problemi "K Most Frequent Words" adıyla raporladı. Top K Frequent Elements'ten (LeetCode 347) farkı iki noktada: sonuç sıralı isteniyor ve eşitlik kuralı deterministik. İkisi de comparator'ı doğru kurmayı gerektiriyor.

Netleştirme soruları

• k, farklı kelime sayısından büyük olabilir mi? (LeetCode garanti ediyor; gerçek bir sistemde tüm kelimeleri döndürmek makul.)
• "Sözlük sırası" neye göre? Sadece küçük harf İngilizce mi, yoksa büyük harf, Türkçe karakter ya da Unicode var mı? (String.compareTo UTF-16 kod birimine göre karşılaştırır; Türkçe alfabetik sıra için Collator gerekir.)
• Büyük-küçük harf aynı kelime sayılmalı mı?
• Veri belleğe sığıyor mu, yoksa stream mi?

İpuçları

Yaklaşım

Adım 1, sayma: frequency.merge(word, 1, Integer::sum) ile O(n). n kelime sayısı, m farklı kelime sayısı. (Kelime uzunluğu L ise hash ve karşılaştırmalar O(L) sürer; aşağıdaki karmaşıklıklar L'yi sabit sayıyor.)

Taban çizgisi, sırala: Girdileri "sıklık azalan, eşitlikte kelime artan" sırasına göre diz, ilk k'yı al. O(n + m log m). Kısa, okunaklı ve m küçükken en doğru seçim; mülakatta ilk söylenmesi gereken çözüm.

Boyutu k olan min-heap: Heap'in tepesinde, yeni aday geldiğinde ilk atılacak eleman durur. Bu yüzden comparator "en kötü önce" mantığıyla kurulur:

1. Sıklık küçük olan önce (tepede),
2. Sıklıklar eşitse sözlük sırasında büyük olan önce (çünkü sonuçta o daha geride kalacak).

Her girdiyi ekle, boyut k'yı aşarsa tepeyi at. Sonunda heap'te en iyi k kelime kalır; poll ile kötüden iyiye çıkarıp listeyi ters çevir. O(n + m log k) zaman, O(m + k) bellek.

Comparator tuzağı: En sık hata, "sonuç alfabetik artan olmalı" diye heap'te de alfabetik artan sıra kullanmak. ["a", "b", "c"], k = 2 için böyle bir heap tepeye "a"'yı koyar, üçüncü eleman gelince "a"'yı atar ve sonuç ["c", "b"] olur; doğrusu ["a", "b"]. Heap'in sırası, sonucun sırasının tam tersidir: sıklık için de, eşitlik kuralı için de. Bu tuzak testlerde ayrıca gösterildi.

İkinci yaygın hata, comparator'da sıklıkları a.getValue() - b.getValue() ile çıkarmak. Sayılar burada küçük olduğu için taşma olmaz ama alışkanlık olarak Integer.compare ya da Map.Entry.comparingByValue() kullanılmalı.

Alternatifler: Bucket sort (index = sıklık) O(n + m log m) kalır, çünkü her kovanın içini alfabetik sıralamak gerekir; ama kovalar küçükse pratikte hızlıdır. Bir trie'yi her kovada kullanmak alfabetik sırayı bedavaya verir ama mülakatta aşırı mühendislik olur. Max-heap'e her şeyi koyup k kez poll etmek O(m + k log m)'dir (heapify O(m)), k ≪ m iken iyidir ama tüm girdileri bellekte heap olarak tutar.

Java çözümü

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public final class TopKFrequentWords {

    // Tepede "ilk atılacak aday": frekansı küçük olan; eşitlikte sözlükte SONRA gelen.
    private static final Comparator<Map.Entry<String, Integer>> WORST_FIRST =
            Map.Entry.<String, Integer>comparingByValue()
                    .thenComparing(Map.Entry.comparingByKey(Comparator.reverseOrder()));

    // Boyutu k olan min-heap: O(n + m log k) zaman, O(m + k) bellek.
    public List<String> topKFrequent(String[] words, int k) {
        if (k <= 0) {
            return List.of();
        }
        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) {
            frequency.merge(word, 1, Integer::sum);
        }
        PriorityQueue<Map.Entry<String, Integer>> worstOnTop = new PriorityQueue<>(WORST_FIRST);
        for (Map.Entry<String, Integer> entry : frequency.entrySet()) {
            worstOnTop.offer(entry);
            if (worstOnTop.size() > k) {
                worstOnTop.poll();                                 // en zayıf aday elenir
            }
        }
        List<String> result = new ArrayList<>(worstOnTop.size());
        while (!worstOnTop.isEmpty()) {
            result.add(worstOnTop.poll().getKey());                // kötüden iyiye boşalır
        }
        Collections.reverse(result);                               // iyiden kötüye çevir
        return result;
    }

    // Taban çizgisi: hepsini sırala. O(n + m log m).
    public List<String> topKFrequentBySorting(String[] words, int k) {
        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) {
            frequency.merge(word, 1, Integer::sum);
        }
        return frequency.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue(Comparator.reverseOrder())
                        .thenComparing(Map.Entry.comparingByKey()))
                .limit(Math.max(k, 0))
                .map(Map.Entry::getKey)
                .toList();
    }
}

Sözleşme: k <= 0 için boş liste, k farklı kelime sayısından büyükse tüm kelimeler sıralı döner. Sözlük sırası String.compareTo'dur (UTF-16 kod birimi): büyük harfler küçüklerden önce gelir ve Türkçe karakterler (ç, ğ, ş) alfabedeki yerlerinde değil, kod noktalarına göre sıralanır.

Karmaşıklık

n: kelime sayısı, m: farklı kelime sayısı. Kelime uzunluğu sabit sayıldı.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. 5.000 rastgele girdi (0-24 kelime, 9 kelimelik bir sözlükten, k -1 ile 9 arası) için heap ve sıralama versiyonları, bağımsız yazılmış bir brute force ile (iç içe döngüyle sayma, k kez en iyiyi seçme) birebir aynı listeyi üretti. Eşitlik kuralı deterministik olduğu için burada cevap tektir ve doğrudan eşitlik kontrol edilebilir.

Mülakatçı için

Top-K ailesinin "comparator'ı gerçekten anlıyor mu?" sorusu. 347'yi çözen adayların önemli bir kısmı burada eşitlik kuralını heap'e ters yönde yazar ve testte yanlış kelimenin elendiğini görmez. Gözlenecek noktalar: sayma ve seçmeyi ayırması, heap'in tepesinde "atılacak adayın" durduğunu söylemesi, eşitlik kuralını da bu mantıkla tersine çevirmesi ve heap'ten çıkan sırayı ters çevirmeyi unutmaması. Java tarafında Comparator.comparing...thenComparing zincirini ve reverseOrder kullanımını rahat yazması, banka gibi Java ağırlıklı şirketlerde ayrıca sinyal verir.

İpucu zamanlaması: Aday sıralamayla bitirirse "m on milyon, k on ise?" diye sor. Heap'i kurup eşitlik kuralını ters yazarsa ["a", "b", "c"], k = 2 ile elle yürütmesini iste; hatayı kendisi bulmalı.

Takip soruları:

1. Kelimeler sürekli bir log stream'inden geliyor; son 5 dakikanın en sık 10 hata mesajı her saniye istenecek. (Beklenen: saniyelik kovalar + kayan pencere sayacı; bellek sınırlıysa Count-Min Sketch ve küçük bir heap, ya da Space-Saving; sonucun yaklaşık olduğunu kabul etmek.)
2. Sıralama Türkçe alfabeye göre olsun ("çilek" "ceviz"den sonra, "dut"tan önce gelsin). (Beklenen: Collator.getInstance(Locale.forLanguageTag("tr")) ile comparator; String.compareTo'nun kod noktası sırası olduğunu bilmek; büyük-küçük harf için Locale farkındalığı.)
3. Kelimeler 50 sunucuya dağılmış; global top 10 nasıl bulunur? (Beklenen: her sunucunun yerel top 10'u yetmez; kelimeye göre bölümleyip tam sayımları birleştirmek ya da iki turlu bir eşik algoritması.)

Benzer problemler

• Top K Frequent Elements (LeetCode 347) (bu sette: top-k-frequent-elements).
• Sort Characters By Frequency (LeetCode 451): bucket.
• K Closest Points to Origin (LeetCode 973): boyutu k heap.
• Kth Largest Element in an Array (LeetCode 215): heap ya da quickselect.
• Find Median from Data Stream (LeetCode 295) (bu sette: find-median-from-data-stream).