Wawancara Koding: Menyelesaikan Alien Dictionary dengan Topological Sort

Prompt dan Konteks yang Berlaku

Diberikan sebuah array words berisi string ASCII huruf kecil tidak kosong, asumsikan array tersebut diklaim terurut berdasarkan alfabet yang tidak diketahui. Kembalikan urutan apa pun yang memuat setiap karakter unik dalam input tepat satu kali dan membuat daftar kata tersebut terurut. Kembalikan string kosong jika urutan semacam itu tidak ada. Jika beberapa alfabet dapat digunakan, salah satu di antaranya dapat diterima.

Untuk versi wawancara, asumsikan paling banyak 10.000 kata dan paling banyak 100.000 karakter secara total. Ini adalah batasan latihan, bukan batas dari platform tertentu. Untuk ["wrt", "wrf", "er", "ett", "rftt"], salah satu jawabannya adalah "wertf". Daftar ["abc", "ab"] tidak mungkin karena kata yang lebih panjang mendahului prefiksnya sendiri. Daftar ["z", "x", "z"] tidak mungkin karena menyiratkan z < x dan x < z sekaligus.

Bagian yang sulit muncul sebelum topological sort. Input menyediakan kata-kata yang terurut; edge graf harus disimpulkan. Solusi yang benar harus menyimpulkan secara tepat batasan yang dibenarkan oleh perbandingan leksikografis, mempertahankan karakter yang tidak memiliki edge, dan membedakan prefiks yang tidak valid dari siklus berarah.

Apa yang Dievaluasi Pewawancara

Sinyal pertama adalah apakah kandidat menurunkan edge dari karakter pertama yang berbeda dari dua kata yang berdekatan. Jika "wrt" muncul sebelum "wrf", perbandingan tersebut membuktikan t < f. Karakter-karakter setelah perbedaan pertama itu tidak mengungkapkan apa pun tentang pasangan ini karena perbandingan leksikografis telah ditentukan.

Sinyal kedua adalah penalaran prefiks. Ketika semua karakter yang dibandingkan cocok, kata yang lebih pendek harus muncul lebih dulu. "ab" sebelum "abc" tidak menambahkan edge dan tetap valid; "abc" sebelum "ab" bertentangan dengan setiap kemungkinan alfabet. Topological sorting saja tidak dapat menemukan kontradiksi ini karena tidak membuat edge apa pun.

Sinyal ketiga adalah konstruksi graf yang lengkap. Setiap karakter yang diamati membutuhkan sebuah node, termasuk karakter terisolasi dari input satu kata. Bukti berulang untuk edge yang sama tidak boleh menambahkan indegree dua kali. Sebuah set per node sumber menjaga adjasensi dan indegree tetap konsisten.

Sinyal terakhir adalah pembuktian dan validasi. Algoritma Kahn mengembalikan urutan lengkap hanya ketika algoritma tersebut menghapus setiap node. Output yang lebih pendek membuktikan adanya siklus yang tersisa. Beberapa pilihan dengan zero-indegree berarti bukti yang ada tidak menentukan satu alfabet unik; hal tersebut valid di bawah kontrak dasar dan tidak boleh salah diklasifikasikan sebagai sebuah error.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Apakah input mencakup setiap karakter dalam alfabet? Jawaban ini mengurutkan setiap karakter yang diamati

dalam kata-kata. Jawaban ini tidak dapat menciptakan atau menempatkan karakter yang tidak terlihat tanpa definisi alfabet eksternal.

• Apakah sembarang urutan valid dapat diterima? Masalah dasar menerima urutan apa pun. Mengharuskan hasil terkecil berdasarkan

urutan karakter bahasa host membutuhkan min-heap dan mengubah kompleksitas.

• Bagaimana ketidakmungkinan harus direpresentasikan? Kontrak ini menggunakan string kosong baik untuk

prefiks tidak valid maupun siklus. API produksi dapat mengembalikan alasan terstruktur dan witness.

• Apa yang dimaksud dengan karakter? Input dasar berisi huruf ASCII kecil. Unicode code point atau grapheme

cluster memerlukan kontrak tokenisasi sebelum konstruksi graf.

• Bolehkah kata berulang? Ya. Kata berdekatan yang sama tidak menambahkan batasan. Hal itu tidak membuat kamus menjadi tidak valid.
• Haruskah alfabetnya unik? Tidak. Pertanyaan lanjutan dapat mendeteksi keunikan dengan memeriksa jumlah node

zero-indegree yang tersedia di setiap langkah.

• Bisakah input berupa kosong? Versi ini membutuhkan setidaknya satu kata tidak kosong. Jika input kosong diperbolehkan,

konfirmasikan apakah hasil yang diharapkan adalah alfabet kosong atau permintaan tidak valid.

Kerangka Jawaban 30 Detik

“Saya akan membuat node graf untuk setiap karakter unik. Untuk setiap pasangan kata yang berdekatan, saya memindai hingga perbedaan pertama; hal itu menghasilkan satu edge berarah dari karakter kata sebelumnya ke karakter kata setelahnya. Jika tidak ada perbedaan dan kata sebelumnya lebih panjang, urutan prefiks tersebut tidak mungkin, jadi saya mengembalikan string kosong. Saya menghapus duplikasi edge sambil mempertahankan indegree, lalu menjalankan topological sort Kahn dari semua karakter ber-indegree nol. Jika saya memproses setiap node, hasilnya menghormati setiap perbandingan yang disimpulkan; jika saya memproses lebih sedikit node, siklus membuat kamus tidak konsisten. Total waktu adalah linear terhadap karakter input ditambah graf, dan beberapa urutan topologis yang valid dapat diterima.”

Pembahasan Mendalam Langkah demi Langkah

Misalkan C adalah jumlah total karakter di semua kata, U adalah jumlah karakter unik, dan E adalah jumlah edge presedensi yang unik. Inisialisasi graph[ch] sebagai set dan indegree[ch] sebagai nol untuk setiap karakter yang ditemui. Inisialisasi ini diperlukan sebelum membandingkan kata-kata: sebuah karakter bisa valid dan tidak memiliki batasan, sehingga titik ujung edge saja tidak mendefinisikan himpunan node.

Bandingkan hanya kata-kata yang berdekatan. Perbandingan yang berdekatan sudah cukup karena membuktikan setiap pasangan bertetangga terurut akan membuktikan seluruh daftar terurut secara transitivitas. Hal ini juga menghindari jumlah perbandingan pasangan kata yang kuadratik. Untuk pasangan first dan second, periksa posisi yang cocok hingga panjang yang lebih pendek:

1. Pada ketidakcocokan pertama first[i] != second[i], tambahkan first[i] -> second[i] dan hentikan perbandingan pasangan tersebut.
2. Jika setiap posisi bersama cocok dan first lebih panjang, kembalikan string kosong.
3. Jika setiap posisi bersama cocok dan first tidak lebih panjang, jangan tambahkan edge apa pun.

Hanya edge yang baru dimasukkan yang menambah indegree tujuan. Misalkan baik "za" < "zb" maupun "ca" < "cb" menyiratkan a -> b. Menghitung edge tersebut dua kali akan membuat b memiliki indegree positif setelah a dihapus dan secara salah melaporkan siklus.

Algoritma Kahn memasukkan setiap karakter ber-indegree nol ke dalam antrean. Invariannya adalah: untuk setiap karakter yang belum diproses, indegree sama dengan jumlah edge masuk dari karakter lain yang belum diproses; antrean memuat tepat karakter-karakter yang tidak memiliki pendahulu tersebut. Menghapus karakter dari antrean adalah aman. Mengurangi setiap tetangga keluar memodelkan penghapusan edge-edge tersebut, dan tetangga masuk ke dalam antrean saat pendahulu terakhirnya yang belum terpenuhi hilang.

from collections import deque


def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for first, second in zip(words, words[1:]):
        limit = min(len(first), len(second))

        for index in range(limit):
            before = first[index]
            after = second[index]
            if before == after:
                continue

            if after not in graph[before]:
                graph[before].add(after)
                indegree[after] += 1
            break
        else:
            if len(first) > len(second):
                return ""

    ready = deque(
        char for char, degree in indegree.items() if degree == 0
    )
    order: list[str] = []

    while ready:
        char = ready.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)

    return "".join(order) if len(order) == len(indegree) else ""

Pembuktian memiliki dua lapisan. Pertama, ekstraksi graf adalah sahih (sound): setiap edge berasal dari ketidakcocokan pertama dari pasangan yang berdekatan, sehingga setiap alfabet yang valid harus mematuhinya. Pemeriksaan prefiks menghapus satu-satunya kasus berdekatan di mana tidak ada ketidakcocokan tetapi pengurutan tidak mungkin. Kedua, topological sorting adalah sahih: invarian antrean memastikan setiap karakter output muncul setelah semua pendahulu yang disimpulkan. Oleh karena itu, setiap pasangan kata yang berdekatan terurut, yang membuat seluruh daftar terurut.

Jika algoritma menghasilkan kurang dari U karakter, setiap node yang tersisa memiliki indegree positif. Dimulai dari node mana pun yang tersisa dan berulang kali mengikuti edge masuk pasti akan mengunjungi kembali sebuah node dalam graf berhingga; segmen yang berulang adalah siklus berarah. Tidak ada alfabet linear yang dapat memenuhi siklus tersebut. Sebaliknya, graf asiklik selalu memiliki node ber-indegree nol, sehingga algoritma Kahn pada akhirnya menghapus semua node dan mengembalikan urutan yang valid.

Membangun semua node dan memindai kata-kata yang berdekatan membutuhkan waktu O(C). Setiap node dan edge unik diproses sekali oleh algoritma Kahn, sehingga total waktu adalah O(C + U + E) dan ruang ekstra adalah O(U + E). Dengan ASCII huruf kecil, U paling banyak 26, tetapi mempertahankan batas simbolik membuat penalaran ini dapat digunakan kembali.

Validasi harus memeriksa properti ketika beberapa jawaban dimungkinkan. Hasil yang tidak kosong harus memuat karakter input unik tepat satu kali. Untuk setiap pasangan yang berdekatan, bandingkan menggunakan map peringkat yang dikembalikan dan konfirmasikan bahwa pasangan tersebut terurut; secara terpisah konfirmasikan bahwa tidak ada kata yang lebih panjang mendahului prefiksnya. Uji satu kata, kata-kata berulang, karakter terisolasi, bukti edge duplikat, prefiks valid, prefiks tidak valid, siklus, rantai, dan graf dengan beberapa node ber-indegree nol.

DFS dengan status putih, abu-abu, dan hitam adalah alternatif yang benar. DFS mendeteksi siklus melalui edge ke node abu-abu dan membalikkan postorder untuk hasilnya. Algoritma Kahn membuat ambiguitas terlihat melalui ready set dan menghindari kekhawatiran kedalaman rekursi, sehingga algoritma ini menjadi rekomendasi yang lebih jelas untuk kontrak ini.

Contoh Jawaban Berkualitas Tinggi

“Pertama-tama saya perlu menyimpulkan urutan parsial dari kata-kata yang terurut. Saya membuat node untuk setiap karakter, termasuk karakter yang tidak pernah berpartisipasi dalam sebuah edge. Untuk setiap pasangan bertetangga, saya memindai hingga ketidakcocokan pertama. Jika pasangannya adalah wrt dan wrf, saya menambahkan t -> f dan berhenti karena posisi selanjutnya tidak dapat memengaruhi perbandingan tersebut. Jika tidak ada ketidakcocokan dan kata pertama lebih panjang, seperti abc sebelum ab, input sudah tidak konsisten.

Saya menyimpan tetangga dalam set sehingga bukti berulang untuk satu relasi hanya menambah indegree satu kali. Kemudian saya menjalankan algoritma Kahn: masukkan semua karakter ber-indegree nol ke antrean, hapus satu ke dalam jawaban, kurangi tetangga keluarnya, dan masukkan tetangga ke antrean ketika indegree-nya mencapai nol. Invariannya adalah bahwa karakter dalam antrean tidak memiliki pendahulu yang tersisa di antara karakter yang belum diproses, sehingga setiap karakter yang dikeluarkan aman.

Jika panjang output sama dengan jumlah karakter unik, setiap edge yang disimpulkan dipatuhi. Edge-edge tersebut ditambah pemeriksaan prefiks membuat setiap pasangan kata yang berdekatan terurut, sehingga seluruh daftar terurut. Jika panjangnya lebih pendek, graf yang tersisa mengandung siklus dan tidak ada alfabet yang berfungsi. Runtime-nya adalah O(C + U + E) dengan ruang O(U + E). Saya akan menguji kata yang lebih panjang sebelum prefiksnya, siklus dua edge, bukti duplikat untuk satu edge, satu kata tunggal, dan kasus dengan beberapa output valid; untuk kasus terakhir saya akan memvalidasi properti pengurutan daripada mengharapkan satu string tertentu.”

Kesalahan Umum

• Menggunakan setiap posisi yang berbeda dalam pasangan kata → posisi berikutnya tidak berpartisipasi setelah

ketidakcocokan pertama menentukan urutan leksikografis → tambahkan hanya edge ketidakcocokan pertama dan berhenti.

• Hanya menjalankan topological sort → "abc" sebelum "ab" tidak membuat edge dan lolos → **periksa

kontradiksi kata-lebih-panjang-sebelum-prefiks selama perbandingan pasangan.**

• Membuat node hanya saat menambahkan edge → karakter terisolasi hilang dari jawaban → **inisialisasi

node untuk setiap karakter yang diamati.**

• Menambah indegree untuk edge duplikat → node valid tidak pernah mencapai nol → **gunakan adjacency set

dan tambahkan hanya pada penyisipan pertama.**

• Mengembalikan hasil parsial saat antrean kosong → batasan siklik tampak berhasil → **haruskan

panjang output sama dengan jumlah karakter unik.**

• Menuntut satu jawaban pasti → urutan parsial yang valid dapat memiliki beberapa ekstensi linear → **uji

urutan yang dikembalikan terhadap karakter, edge, dan perbandingan kata.**

• Membandingkan setiap pasangan kata → beban kerja dapat menjadi kuadratik terhadap jumlah kata → **perbandingan yang

berdekatan sudah cukup untuk memastikan urutan terurut.**

• Mengklaim ambiguitas berarti input tidak valid → beberapa alfabet dapat menjelaskan bukti yang sama → **kembalikan

urutan valid apa pun kecuali keunikan adalah bagian dari kontrak.**

Pertanyaan Lanjutan dan Jawabannya

Lanjutan 1: Bagaimana cara menentukan apakah alfabet tersebut unik?

Selama algoritma Kahn, periksa ready set sebelum setiap penghapusan. Jika set tersebut pernah memuat lebih dari satu karakter, setidaknya dua pilihan dapat ditukar menjadi urutan topologis valid yang berbeda, sehingga buktinya ambigu. Jika set selalu memuat tepat satu karakter dan setiap node diproses, urutannya unik. Ready set yang kosong sebelum penyelesaian tetap berarti adanya siklus.

Lanjutan 2: Bagaimana cara mengembalikan hasil valid terkecil berdasarkan urutan karakter normal?

Ganti antrean dengan min-heap yang menggunakan urutan karakter bahasa host sebagai kuncinya. Memilih karakter valid terkecil saat ini menghasilkan ekstensi linear terkecil dengan argumen greedy exchange. Waktunya menjadi O(C + E + U log U); nyatakan dengan jelas bahwa pemutus seri (tie-breaker) ini bersifat eksternal terhadap alfabet alien.

Lanjutan 3: Bagaimana Anda mengembalikan penjelasan yang berguna untuk input yang tidak valid?

Untuk kontradiksi prefiks, kembalikan dua kata yang berdekatan dan indeksnya. Untuk siklus, jalankan DFS tiga warna pada graf yang tersisa setelah Kahn macet, simpan pointer parent, dan rekonstruksi karakter-karakter yang membentuk satu siklus back-edge. Hasil terstruktur dapat membedakan invalid_prefix, cycle, dan valid tanpa membebani (overloading) string kosong.

Lanjutan 4: Bisakah Anda memproses daftar kata sebagai stream?

Simpan kata sebelumnya, tambahkan node dari setiap kata baru, dan turunkan satu batasan pasangan berdekatan ketika kata berikutnya tiba. Graf dan indegree masih perlu disimpan hingga stream berakhir karena bukti selanjutnya dapat menambahkan pendahulu atau membuat siklus. Jalankan topological sort hanya setelah semua kata diamati kecuali sumber menyediakan batas finalisasi.

Lanjutan 5: Bagaimana Anda mengenumerasi setiap alfabet yang valid?

Gunakan backtracking pada semua karakter ber-indegree nol saat ini. Pilih satu, hapus edge keluarnya, lakukan rekursi, lalu kembalikan state. Cara ini hanya mengenumerasi urutan yang valid, tetapi outputnya dapat mendekati U!; konfirmasikan alfabet berukuran kecil atau batasan output sebelum mengimplementasikannya.

Lanjutan 6: Apa yang berubah untuk kata-kata Unicode?

Tentukan unit perbandingan terlebih dahulu. Code point tidak selalu cocok dengan karakter yang dirasakan pengguna, dan collation locale dapat memperlakukan bentuk yang dinormalisasi atau urutan multi-code-point secara khusus. Lakukan tokenisasi pada setiap kata sesuai dengan simbol alfabet yang dinyatakan, lakukan normalisasi hanya jika kontrak mengharuskannya, lalu jalankan algoritma graf yang sama di atas token. Tanpa kontrak tersebut, “urutan karakter” menjadi kurang terspesifikasi.