Wawancara Koding: Bagaimana Anda mengembalikan K kata yang paling sering muncul?

Petunjuk dan konteks

Diberikan sebuah array words dan integer k, kembalikan k kata yang paling sering muncul. Selesaikan hasil seri dengan urutan leksikografis menaik.

Wawancara ini berfokus pada mempertahankan kumpulan kandidat berukuran k dan memutuskan apakah root heap mewakili kandidat terburuk atau terbaik. Java hanya digunakan untuk mendemonstrasikan komparator; algoritmanya tidak bergantung pada bahasa tertentu.

Apa yang diuji oleh pewawancara

Penghitungan

Gunakan hash map untuk menghitung setiap kata dan membedakan panjang array n dari jumlah kata unik m.

Aturan pengurutan

Frekuensi lebih tinggi menang; frekuensi yang sama menggunakan urutan leksikografis yang lebih kecil. Root min-heap harus menjadi kandidat yang lebih buruk sehingga entri yang berlebih dapat dihapus.

Kompleksitas

Pengurutan penuh adalah O(m log m). Heap berukuran k adalah O(n + m log k), berguna ketika k jauh lebih kecil daripada jumlah kata unik.

Kebenaran

Jelaskan mengapa urutan heap untuk pengeluaran berbeda dari urutan keluaran akhir: heap menghapus kandidat terburuk, sedangkan jawabannya harus mencantumkan kandidat terbaik terlebih dahulu.

Pertanyaan klarifikasi yang perlu diajukan

Apakah kata-kata berupa huruf kecil bahasa Inggris dan peka huruf besar-kecil (case-sensitive)?
Apakah k dijamin berada di antara 1 dan jumlah kata unik?
Apakah urutan leksikografis berupa ASCII, Unicode, atau lokal bisnis tertentu?
Apakah input harus diproses sebagai stream?
Apakah output harus stabil, atau urutan apa pun dapat diterima?
Bisakah frekuensi melebihi integer 32-bit?

Kerangka jawaban 30 detik

"Saya akan menghitung frekuensi dengan hash map. Untuk setiap kata unik, saya mempertahankan min-heap berukuran k yang root-nya adalah kandidat yang lebih buruk: frekuensi lebih rendah, atau urutan leksikografis lebih besar jika seri. Setelah memasukkan, saya melakukan pop ketika heap melebihi k. Akhirnya saya mengeluarkan entri heap dalam urutan frekuensi menurun dan urutan leksikografis menaik. Biaya penghitungan adalah O(n), pemeliharaan heap O(m log k), dan ruang adalah O(m)."

Pembahasan mendalam langkah demi langkah

Langkah 1: Hitung frekuensi

Petakan setiap kata ke jumlah kemunculannya. Log streaming dapat menggunakan agregasi eksternal atau penghitung perkiraan, tetapi masalah ini mengasumsikan map kata unik muat dalam memori.

Langkah 2: Tentukan kandidat terburuk

Kandidat A lebih buruk daripada B ketika A memiliki frekuensi lebih rendah; jika seri, A memiliki urutan leksikografis yang lebih besar. Komparator menempatkan kandidat tersebut di root heap.

Langkah 3: Pertahankan ukuran k

Masukkan setiap entri dari frequency map dan lakukan pop ketika heap melebihi k. Dengan demikian, heap mempertahankan k entri yang paling mungkin termasuk dalam jawaban akhir.

Langkah 4: Hasilkan output

Pop pada heap berjalan dari yang terburuk ke yang lebih baik, sehingga tidak dapat dikembalikan secara langsung. Balikkan entri yang dikumpulkan atau urutkan dengan frekuensi menurun dan leksikografis menaik.

Langkah 5: Buktikan kebenaran

Setiap kali ukuran melebihi k, hapus anggota terburuk dari set saat ini. Anggota tersebut tidak dapat mengungguli salah satu dari k anggota yang dipertahankan. Melalui induksi, heap akhir berisi Top K global.

Langkah 6: Tangani batas

Uji k=1, frekuensi yang sama, satu kata unik, banyak duplikat, dan k=m. Komparator tidak boleh membalikkan hasil seri secara tidak sengaja.

Contoh jawaban berkualitas tinggi

java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.merge(word, 1, Integer::sum);
        }

        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
            int byFrequency = Integer.compare(count.get(a), count.get(b));
            if (byFrequency != 0) return byFrequency;
            return b.compareTo(a); // larger lexicographic value is worse
        });

        for (String word : count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) heap.poll();
        }

        List<String> answer = new ArrayList<>();
        while (!heap.isEmpty()) answer.add(heap.poll());
        Collections.reverse(answer);
        return answer;
    }
}

Biaya penghitungan adalah O(n). Dengan m kata unik, operasi heap berbiaya O(log k), menghasilkan total waktu O(n + m log k) dan ruang O(m).

Kesalahan umum

Menempatkan kandidat terbaik di root heap → jawaban yang benar akan dikeluarkan → letakkan kandidat terburuk di root.
Membalikkan komparator untuk kasus seri → urutan output salah → pertahankan kata-kata yang lebih kecil secara leksikografis terlebih dahulu jika frekuensinya sama.
Mengembalikan hasil pop heap secara langsung → output berjalan dari terburuk ke terbaik → balikkan atau lakukan pengurutan akhir.
Mengklaim O(n log k) setelah pengurutan penuh → kompleksitasnya salah → pengurutan penuh berbiaya O(m log m).
Hanya menguji frekuensi yang berbeda → perilaku seri tidak teruji → sertakan frekuensi yang semuanya sama dan banyak hasil seri.
Mengabaikan k=m → pengeluaran yang tidak perlu atau kesalahan batas → izinkan heap untuk menampung semua kata unik.
Menggunakan pengurutan yang bergantung pada lokal secara tidak sengaja → hasil bervariasi di berbagai lingkungan → nyatakan urutan yang diperlukan secara eksplisit.
Menyebutkan hash map tanpa analisis ruang → skala menjadi tidak jelas → nyatakan kompleksitas n, m, dan k.

Pertanyaan lanjutan dan jawabannya

Pertanyaan lanjutan 1: Apakah Anda akan tetap menggunakan heap ketika k mendekati m?

Pengurutan penuh mungkin memiliki konstanta yang lebih baik dan kode yang lebih sederhana. Heap tetap valid, tetapi O(m log k) mendekati O(m log m).

Pertanyaan lanjutan 2: Bagaimana jika inputnya adalah stream tanpa batas?

Penghitungan tepat tetap memerlukan status (state). Gunakan window, agregasi eksternal, atau aproksimasi; Top K yang tepat memerlukan state frekuensi yang dipertahankan secukupnya.

Pertanyaan lanjutan 3: Bagaimana jika kata-kata unik melebihi memori?

Lakukan partition-hash ke disk, hitung setiap partisi, dan gabungkan kandidat, atau gunakan external sorting. Jangan memuat array penuh ke dalam memori.

Pertanyaan lanjutan 4: Bagaimana Anda mendukung kata-kata yang case-insensitive?

Normalisasikan dengan lokal eksplisit sebelum menghitung. Tentukan apakah output mempertahankan ejaan asli dan hindari menghitung bentuk yang setara dua kali.

Pertanyaan lanjutan 5: Bagaimana Anda menguji komparator?

Lakukan pengujian (assert) pada frekuensi yang sama dengan urutan leksikografis berlawanan, k=1, k=m, dan input dengan banyak duplikat; bandingkan kasus acak dengan referensi full-sort.

Sumber 1: LeetCode 692

Masalah ini mendefinisikan frekuensi menurun, hasil seri leksikografis menaik, dan tindak lanjut O(n log k), yang menetapkan target output dan kompleksitas.

Sumber 2: NeetCode Top K

NeetCode mendemonstrasikan pendekatan frequency-map dan Top K serta menyoroti komparator dan pertukaran antara heap dan pengurutan (sort).

Sumber 3: Oracle PriorityQueue

Oracle mendokumentasikan pengurutan PriorityQueue berdasarkan urutan alami atau Comparator, yang mendukung komparator min-heap kustom dan semantik poll.