Trie (önek ağacı) gerçekleme

Problem

Küçük harfli İngilizce kelimeleri saklayan bir trie (önek ağacı) sınıfı yaz:

• insert(word): kelimeyi ekler.
• search(word): kelime daha önce tam olarak eklendiyse true.
• startsWith(prefix): eklenen kelimelerden en az biri bu önekle başlıyorsa true.

insert("kitap")
search("kitap")     -> true
search("kit")       -> false   (yol var ama "kit" bir kelime olarak eklenmedi)
startsWith("kit")   -> true
insert("kit")
search("kit")       -> true
startsWith("kalem") -> false

Netleştirme soruları

• Alfabe ne? Sadece a-z mi? (Evet. Unicode ya da Türkçe karakter gerekseydi düğüm yapısı değişirdi.)
• Boş string eklenebilir ya da aranabilir mi? startsWith("") ne dönmeli? (Her zaman true mantıklı.)
• Silme işlemi gerekiyor mu? (Bu soruda hayır; takip sorusu olarak gelir.)
• Kaç kelime ve ortalama uzunluk ne? (Bellek tahmini için.)
• Thread-safe olması gerekiyor mu?

İpuçları

Yaklaşım

Kaba çözüm: Kelimeleri bir HashSet'te tut. insert ve search ortalama O(L) (hash hesabı). startsWith ise tüm kelimeleri tarar: O(N · L). Alternatif olarak TreeSet ile ceiling(prefix) alınıp önekle başlıyor mu bakılabilir: O(L log N). Bu, Java'da çoğu zaman göz ardı edilen ve gayet iyi olan bir çözümdür.

Trie (seçilen çözüm): Her düğüm 26 çocuk işaretçisi ve bir endOfWord bayrağı tutar. Ortak önekler tek bir yol paylaşır. Üç işlem de sadece kelime uzunluğuna bağlıdır, kaç kelime saklandığına değil.

• insert: kökten başla, her karakter için çocuk yoksa oluştur, ilerle; sonda bayrağı kaldır.
• walk(s): öneki yürü; yol koparsa null.
• search = walk != null && endOfWord; startsWith = walk != null.

Çocuklar için dizi mi, map mi? Node[26] dizisi en hızlısıdır ama her düğüm 26 referans (sıkıştırılmış referanslarla yaklaşık 4 byte × 26 + dizi başlığı ≈ 120 byte) tutar, çoğu boştur. HashMap<Character, Node> seyrek düğümlerde daha az yer kaplayabilir ve büyük alfabeyi destekler, ama kutulama ve hash maliyeti vardır. Mülakatta bu takası söylemek beklenir.

Java çözümü

public final class Trie {

    private static final class Node {
        final Node[] children = new Node[26];             // sadece 'a'..'z'
        boolean endOfWord;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new Node();
            node = node.children[idx];
        }
        node.endOfWord = true;                            // yol değil, kelime olduğunu işaretle
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.endOfWord;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    /** Ön ekin bittiği düğümü döner; yol yoksa null. */
    private Node walk(String s) {
        Node node = root;
        for (int i = 0; i < s.length() && node != null; i++) {
            node = node.children[s.charAt(i) - 'a'];
        }
        return node;
    }
}

Node statik iç sınıf olarak tanımlandı; statik olmayan iç sınıf her düğümde dış Trie nesnesine gizli bir referans taşırdı. walk yardımcısı search ve startsWith arasındaki kod tekrarını kaldırır.

Karmaşıklık

• Zaman: insert, search, startsWith için O(L); L kelime ya da önek uzunluğu.
• Bellek: En kötü O(T · Σ); T toplam karakter sayısı (eklenen düğüm sayısı en fazla T), Σ = 26 dizi boyutu. Ortak önekler bu sayıyı azaltır.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Eklenen kelimeyi bulma; öneki kelime olarak bulamama (kit), sonra kit eklenince bulma.
• Olmayan önek: false.
• Boş önek: true.
• Eklenenden uzun kelime (kitaplar): false; yol erken kopuyor.
• Aynı kelimeyi iki kez eklemek: sorun yok.
• 50 tur × 400 rastgele işlem (alfabe a-c, uzunluk 1-5), HashSet + startsWith taramasıyla çalışan referansa karşı karşılaştırıldı.

Mülakatçı için

Bu soru bir "tasarım + veri yapısı" ısınmasıdır; kod kısa olduğu için asıl ayırt edici unsur netlik ve takaslardır. Gözlemle: endOfWord bayrağını unutup search'ü startsWith gibi yazıyor mu? search ile startsWith'in ortak kısmını bir yardımcıya çıkarıyor mu? Dizi/map takasını ve bellek maliyetini biliyor mu?

İpucu zamanlaması: Trie'yi hiç duymamış bir aday için ilk iki ipucu yapıyı tarif eder; bu durumda soruyu "yeni bir yapıyı kavrayıp uygulama" sorusu olarak değerlendir. Trie'yi bilen aday ipucu olmadan 10-15 dakikada bitirmelidir; kalan süreyi takip sorularına ayır.

Takip sorusu 1: delete(word) ekle; artık kullanılmayan düğümler de silinsin. Beklenen: bayrağı indirmek ve geri dönerken çocuğu ve bayrağı olmayan düğümleri ebeveynden kopartmak (özyinelemeli ya da yol stack'iyle). Her düğümde "altındaki kelime sayısı" tutmak silmeyi ve "bu önekle kaç kelime var" sorgusunu kolaylaştırır.

Takip sorusu 2: Arama kutusu için otomatik tamamlama: önek verildiğinde en popüler 5 kelimeyi döndür. Beklenen: her düğümde top-5 listesini önceden hesaplayıp tutmak (okuma O(L), yazma maliyetli) ya da önek düğümünden DFS + heap. Production'da Elasticsearch completion suggester ya da edge n-gram indeksleri.

Takip sorusu 3: Trie bellekte 2 GB tutuyor. Nasıl küçültürsün? Beklenen: tek çocuklu zincirleri birleştiren radix tree (sıkıştırılmış trie), ortak sonekleri de paylaşan DAWG/FST (Lucene'in terim sözlüğü FST kullanır), dizi yerine seyrek çocuk gösterimi.

Benzer problemler

• Design Add and Search Words Data Structure (LeetCode 211)
• Word Search II (LeetCode 212)
• Replace Words (LeetCode 648)
• Search Suggestions System (LeetCode 1268)
• Longest Word in Dictionary (LeetCode 720)