Permintaan dan konteks
Implementasikan ART yang menyimpan kunci dan nilai byte dengan panjang bervariasi beserta operasi penyisipan, pencarian tepat, pencocokan prefiks terpanjang, dan penghapusan. Simpul beradaptasi di antara Node4, Node16, Node48, dan Node256; kompresi jalur harus mempertahankan semantik kunci. Ini adalah pertanyaan coding tentang compressed tree, indeks, dan tata letak memori.
Apa yang dievaluasi pewawancara
- Menangani jalur terkompresi, terminasi kunci, dan byte arbitrer alih-alih hanya karakter.
- Mempertahankan peningkatan (upgrade) dan penurunan (downgrade) di antara keempat jenis simpul.
- Mengimplementasikan pencocokan prefiks terpanjang dan membedakan kecocokan tepat dari nilai leluhur (ancestor).
- Membuktikan bahwa penghapusan mempertahankan invarian kompresi.
- Menjelaskan kompleksitas, kompromi memori, dan konkurensi.
Pertanyaan klarifikasi yang perlu diajukan
- Apakah kunci berupa string byte buram (opaque) dan bisakah mengandung byte nol?
- Bisakah simpul internal menyimpan nilai, atau hanya simpul daun (leaf)?
- Berapa panjang prefiks dan sisa yang harus dikembalikan oleh pencarian prefiks terpanjang?
- Apakah penghapusan harus langsung menyusutkan ukuran, atau dapatkah reklamasi ditangguhkan?
- Apakah pembacaan lock-free atau publikasi snapshot diperlukan?
Jawaban 30 detik
"Saya membandingkan byte buram dan menyimpan prefiks terkompresi beserta nilai terminasi pada simpul internal. Simpul renggang (sparse) menggunakan Node4/16; simpul padat (dense) ditingkatkan ke Node48/256. Penghapusan menurunkan tipe simpul dan menggabungkan jalur anak tunggal yang tidak memiliki nilai. Pencarian tepat menghabiskan seluruh kunci; pencarian prefiks terpanjang mencatat simpul bernilai terdekat. Saya akan membuktikan invarian single-threaded terhadap peta referensi sebelum menambahkan lock atau snapshot yang tidak dapat diubah (immutable)."
Jawaban mendalam
Langkah 1: Tentukan simpul dan daun
Simpul internal menyimpan prefiks terkompresi, panjangnya, nilai opsional, dan anak-anak yang diindeks oleh byte berikutnya. Daun menyimpan kunci lengkap atau referensi nilai unik, yang menangani kasus ketika satu kunci menjadi prefiks dari kunci lainnya.
Node { prefix, prefixLen, hasValue, value, children }
Leaf { key, value }Panjang prefiks bersifat eksplisit karena kunci adalah byte arbitrer, bukan string yang diakhiri null.
Langkah 2: Menyisipkan dan membagi (split)
Bandingkan prefiks simpul dengan sisa kunci. Jika cocok, lanjutkan atau perbarui nilainya. Jika divergen, buat induk yang berisi prefiks umum dan lampirkan simpul lama serta daun baru di bawah byte perbedaannya. Jika kunci baru berakhir pada prefiks umum, setel tanda nilai pada induk.
Langkah 3: Pilih tata letak adaptif
Node4 dan Node16 menyimpan array kunci dan pointer yang ringkas; pencarian dapat memindainya atau menggunakan perbandingan vektor. Node48 memetakan semua 256 kemungkinan byte ke dalam 48 slot pointer, menghindari 256 pointer residen. Node256 mengindeks langsung berdasarkan byte. Lakukan upgrade dengan menyalin anak tanpa kehilangan status prefiks atau nilai.
Langkah 4: Pencarian tepat dan prefiks terpanjang
Pencarian tepat harus menghabiskan setiap byte kunci dan mencapai hasValue atau kunci daun yang setara. Pencarian prefiks terpanjang mencatat kandidat setiap kali sebuah simpul memiliki nilai, kemudian melanjutkan melalui byte berikutnya hingga gagal atau habis, lalu mengembalikan kandidat terakhir beserta panjangnya.
Langkah 5: Hapus dan susutkan
Setelah menghapus nilai, hapus simpul yang tidak memiliki anak. Jika simpul tanpa nilai memiliki satu anak, gabungkan prefiks dan byte tepinya ke dalam simpul anak tersebut. Turunkan Node256, Node48, Node16, dan Node4 pada ambang batas jumlah anak yang terdokumentasi. Pertahankan kunci lengkap daun selama penggabungan.
Langkah 6: Invarian dan kompleksitas
Menggabungkan prefiks, byte tepi, dan daun di sepanjang jalur akar-ke-daun mana pun harus menghasilkan kunci asli. Simpul internal tidak boleh memiliki byte tepi duplikat; hasValue berarti kunci berakhir tepat di sana. Dengan panjang kunci L, pencarian adalah O(L); tata letak adaptif menghindari alokasi 256 slot untuk simpul renggang.
Langkah 7: Uji dan tambahkan konkurensi
Bandingkan operasi acak penyisipan, pencarian, penghapusan, dan prefiks terpanjang dengan peta referensi. Sertakan kunci kosong, byte nol, kunci prefiks, dan semua 256 percabangan. Mulai versi konkuren dengan read-write lock; baru kemudian pertimbangkan copy-on-write, epoch, atau RCU, karena reklamasi memori harus aman sebelum mengekspos pointer lock-free.
Jawaban model
"Saya memperlakukan kunci sebagai string byte buram. Simpul membawa prefiks terkompresi, nilai terminasi opsional, dan anak. Kecocokan parsial membagi induk prefiks umum; jumlah anak meningkatkan Node4, 16, 48, dan 256, sementara penghapusan menurunkan tipe dan menggabungkan jalur anak tunggal. Pencarian tepat menghabiskan seluruh kunci; pencarian prefiks terpanjang mengingat simpul bernilai terdekat.
Setiap jalur harus dapat merekonstruksi kunci asli. Pengujian acak membandingkan hasilnya dengan sebuah peta dan mencakup byte nol, kunci kosong, kunci prefiks, dan cabang yang padat. Setelah kebenaran single-threaded tercapai, gunakan lock; desain copy-on-write atau lock-free juga memerlukan epoch atau reklamasi aman yang setara."
Kesalahan umum
- Memperlakukan kunci sebagai karakter → kunci biner dan byte nol gagal → bandingkan panjang byte dan nilainya.
- Melupakan nilai internal → kunci prefiks tidak dapat cocok → pertahankan
hasValue. - Memberikan 256 pointer pada Node48 → kehilangan penghematan memori simpul renggang → gunakan peta indeks.
- Menghapus nilai tanpa menggabungkan → meninggalkan jalur kosong → susutkan pada ambang batas.
- Mengabaikan kandidat leluhur → pencarian prefiks terpanjang melewatkan kecocokan → ingat simpul bernilai terakhir.
- Mempublikasikan pointer mentah tanpa reklamasi aman → pembaca menggunakan memori yang telah dibebaskan → mulai dengan lock, lalu epoch/RCU.
Pertanyaan lanjutan dan tanggapan
Pertanyaan lanjutan 1: Mengapa tidak selalu menggunakan Node256?
Sebagian besar simpul bersifat renggang, sehingga 256 slot membuang-buang memori. Tata letak adaptif menyeimbangkan wilayah yang renggang dan padat.
Pertanyaan lanjutan 2: Bagaimana jika satu kunci adalah prefiks dari kunci lainnya?
Simpan nilai kunci yang lebih pendek pada simpul internal dan pertahankan anak-anak untuk kunci yang lebih panjang.
Pertanyaan lanjutan 3: Kapan Anda melakukan penggabungan setelah penghapusan?
Gabungkan simpul tanpa nilai yang memiliki satu anak dengan merangkaikan prefiks dan byte tepinya, dengan tetap mempertahankan kunci daun.
Pertanyaan lanjutan 4: Bagaimana Anda mempublikasikan snapshot konkuren?
Gunakan copy-on-write untuk akar baru yang immutable dan lakukan reklamasi pohon lama dengan epoch atau penghitungan referensi (reference counting).