Wawancara Koding: Mengimplementasikan Radix Tree untuk Perutean Prefiks

Petunjuk dan konteks

Anda diberikan kunci string seperti /api, /api/users, dan /api/users/admin. Implementasikan radix tree di mana setiap edge menyimpan string yang tidak kosong dan setiap node dapat memegang sebuah nilai. Dukung insert(key, value), get(key), longestPrefix(key), dan delete(key). Kunci kosong hanya diizinkan sebagai nilai root. Pewawancara menginginkan struktur data dan penalaran logis, bukan pemanggilan pustaka bawaan.

Apa yang dinilai oleh pewawancara

• Apakah Anda mempertahankan invarian bahwa setiap label edge non-root tidak boleh kosong dan node saudara (sibling) memiliki karakter pertama yang berbeda?
• Bisakah Anda memecah edge pada ketidakcocokan pertama tanpa kehilangan subtree atau nilai apa pun?
• Bisakah Anda membedakan exact lookup dari longest-prefix lookup?
• Apakah Anda mengompresi node unary tanpa nilai setelah penghapusan dan menyatakan kompleksitas sebenarnya berdasarkan panjang kunci?

Pertanyaan klarifikasi yang perlu diajukan

Tanyakan apakah kunci berupa byte atau Unicode code point, apakah pencocokan bersifat case-sensitive, apakah penyisipan duplikat akan menggantikan nilai, dan apakah diperlukan akses konkuren. Tanyakan apakah longestPrefix mengembalikan kunci yang cocok, nilainya, atau keduanya. Implementasi berorientasi byte adalah yang paling sederhana dan membuat kompleksitas bergantung pada byte; normalisasi Unicode berada di luar pohon kecuali jika diminta secara eksplisit. Jika konkurensi diperlukan, tambahkan sinkronisasi di sekitar struktur daripada secara diam-diam mengklaim algoritma tersebut aman untuk thread (thread-safe).

Kerangka jawaban 30 detik

Setiap node menyimpan label edge, nilai opsional, dan anak-anak yang diindeks berdasarkan byte pertama mereka. Selama penyisipan, bandingkan sisa kunci dengan label anak. Jika cocok sepenuhnya, turun ke bawah; jika cocok sebagian, pecah anak menjadi node prefiks bersama dan dua node sufiks. Exact lookup hanya berhasil jika seluruh kunci habis di sebuah node yang memiliki nilai. Longest-prefix lookup mengingat nilai terdalam yang ditemui saat menelusuri ke bawah. Penghapusan menghapus nilai dan menggabungkan node dengan anak tunggalnya jika node tersebut tidak memiliki nilai.

Penyelidikan mendalam langkah demi langkah

1. Nyatakan invarian. Root tidak memiliki label edge. Setiap node lainnya memiliki label yang tidak kosong. Tidak ada dua anak dari satu node yang diawali dengan byte yang sama. Sebuah node dapat menyimpan nilai meskipun ia juga memiliki anak, sehingga /api dan /api/users dapat hidup berdampingan.
2. Insert berdasarkan prefiks umum terpanjang. Misalkan p adalah prefiks umum antara sisa kunci dan label anak. Jika p kosong, pilih anak lain. Jika p sama dengan label anak, konsumsi label tersebut dan lakukan rekursi. Jika p lebih pendek, buat induk baru berlabel p, pindahkan anak lama di bawah sufiksnya, lalu lampirkan sufiks kunci baru atau ganti nilainya ketika kunci berakhir di titik pemisahan.
3. Lookup. Exact lookup mengonsumsi satu edge pada satu waktu dan gagal jika ada ketidakcocokan atau anak yang hilang. Untuk longest-prefix lookup, catat nilai root terlebih dahulu, lalu catat setiap node bernilai yang dicapai sebelum kunci berakhir; kembalikan catatan terakhir.
4. Delete dan kompresi. Hapus nilai pada target. Jika node tidak memiliki nilai dan hanya memiliki satu anak, gabungkan kedua label dan promosikan anak-anak dari anak tersebut. Jika memiliki beberapa anak atau masih memiliki nilai, pertahankan node tersebut. Ini menjaga invarian sibling.
5. Kompleksitas. Dengan pemilihan anak menggunakan hash map, setiap operasi membandingkan paling banyak byte kunci input, sehingga waktu adalah O(k) ditambah overhead hash map dan ruang adalah O(total byte kunci yang disimpan). Kompresi jalur mengurangi node unary yang renggang; ini tidak membuat kunci yang panjang berjalan dalam waktu konstan.
6. Uji kasus-kasus ekstrem. Uji kunci kosong dan satu karakter, menyisipkan kunci yang merupakan prefiks dari kunci yang sudah ada, menyisipkan kunci yang memperluas kunci yang sudah ada, memecah di tengah edge, penggantian duplikat, menghapus daun, menghapus nilai prefiks, menghapus satu-satunya kunci, dan kueri longest-prefix tanpa kecocokan.

Contoh jawaban berkualitas tinggi

Saya akan merepresentasikan edge sebagai string byte non-kosong dan menyimpan anak-anak berdasarkan byte pertama mereka. Satu-satunya operasi non-trivial adalah penyisipan: bandingkan label anak dengan sisa kunci, dan pecah pada ketidakcocokan pertama. Pemecahan tersebut membuat node prefiks bersama, mempertahankan sufiks dan subtree lama, serta melampirkan sufiks baru. Lookup mengikuti label lengkap; longest-prefix lookup mengingat node terdalam yang memiliki nilai. Penghapusan menghapus nilai dan menggabungkan node tanpa nilai dengan anak tunggalnya. Berikut adalah bentuk inti pemisahan dalam pseudocode mirip Go:

type node struct {
    label string
    value any
    hasValue bool
    child map[byte]*node
}

// When common is shorter than child.label:
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}

Dalam kode produksi, saya akan menangani kasus di mana newSuffix kosong dengan menyimpan nilai pada parent, dan saya akan membuat penghapusan hanya bergabung ketika hasValue bernilai false dan hanya ada tepat satu anak. Saya akan menguji invarian setelah setiap mutasi, bukan hanya memastikan bahwa contoh lookup berhasil.

Kesalahan umum

• Memperlakukan radix tree sebagai node trie satu karakter → kompresi jalur hilang → simpan label edge non-kosong dan bandingkan seluruh label.
• Memecah edge tetapi menjatuhkan nilai lama atau anak-anaknya → kunci yang ada menghilang → pindahkan node lama ke bawah sufiksnya sebelum melampirkan sufiks baru.
• Mengembalikan nilai cocok pertama untuk longest-prefix lookup → rute yang lebih spesifik terlewatkan → terus perbarui kandidat di setiap node bernilai.
• Menggabungkan node yang masih memiliki nilai → kunci yang lebih pendek terhapus secara tidak sengaja → gabungkan hanya node unary yang tidak bernilai.
• Mengklaim lookup O(1) → kunci masih harus dibandingkan → nyatakan O(k) dalam panjang kunci dan jelaskan biaya pemetaan anak.

Pertanyaan lanjutan dan jawaban

Apa yang berubah jika kunci tidak peka huruf besar/kecil (case-insensitive)?

Normalisasi kunci sebelum penyisipan dan lookup menggunakan satu aturan yang terdokumentasi, seperti ASCII lowercase. Jangan menormalisasi hanya selama lookup; jika tidak, dua ejaan dapat menempati jalur yang tidak konsisten. Penanganan case folding dan normalisasi Unicode harus menjadi kebijakan terpisah yang ditentukan secara jelas.

Bagaimana Anda mendukung segmen rute wildcard?

Tambahkan aturan preseden yang eksplisit, misalnya edge statis sebelum edge parameter sebelum edge catch-all. Invarian radix tetap menangani prefiks literal, tetapi pencocokan menjadi pencarian terhadap jenis edge, jadi tentukan jumlah maksimum cabang wildcard dan uji rute yang ambigu.

Bisakah struktur pohon dibuat aman untuk operasi baca dan tulis konkuren?

Gunakan read-write lock atau snapshot copy-on-write. Klaim lock-free membutuhkan desain memory-reclamation; hanya menggunakan root atomik tidak membuat pemisahan dan penggabungan di tempat aman. Pisahkan invarian algoritmik dan kebijakan sinkronisasi.