Gesaan dan konteks
Laksanakan ART yang menyimpan kunci dan nilai bait panjang boleh ubah dengan penyisipan, carian tepat, pemadanan awalan terpanjang dan pemadaman. Nod menyesuaikan diri antara Node4, Node16, Node48 dan Node256; pemampatan laluan mesti mengekalkan semantik kunci. Ini ialah soalan coding tentang pepohon termampat, indeks dan susun atur memori.
Perkara yang dinilai oleh penemu duga
- Mengendalikan laluan termampat, penamatan kunci dan bait sebarangan dan bukannya aksara sahaja.
- Mengekalkan peningkatan dan penurunan taraf antara keempat-empat jenis nod.
- Melaksanakan pemadanan awalan terpanjang dan membezakan padanan tepat daripada nilai leluhur.
- Membuktikan pemadaman mengekalkan batas tak varian pemampatan.
- Menerangkan kekompleksan, pertukaran memori dan keserentakan.
Soalan penjelasan untuk ditanya
- Adakah kunci merupakan rentetan bait legap dan bolehkah ia mengandungi bait sifar?
- Bolehkah nod dalaman memegang nilai, atau daun sahaja?
- Apakah panjang awalan dan baki yang perlu dikembalikan oleh carian awalan terpanjang?
- Adakah pemadaman mesti mengecil serta-merta, atau penebusgunaan boleh ditangguhkan?
- Adakah bacaan tanpa kunci (lock-free) atau penerbitan snapshot diperlukan?
Jawapan 30 saat
"Saya membandingkan bait legap dan menyimpan awalan termampat berserta nilai penamatan pada nod dalaman. Nod jarang menggunakan Node4/16; nod tumpat dinaik taraf kepada Node48/256. Pemadaman menurunkan taraf dan menggabungkan laluan anak tunggal tanpa nilai. Carian tepat menggunakan keseluruhan kunci; carian awalan terpanjang merekodkan nod bernilai yang paling hampir. Saya akan membuktikan batas tak varian benang tunggal terhadap peta rujukan sebelum menambah kunci atau snapshot tidak boleh ubah."
Jawapan mendalam
Langkah 1: Tentukan nod dan daun
Nod dalaman menyimpan awalan termampat, panjangnya, nilai pilihan dan anak yang diindeks oleh bait seterusnya. Daun menyimpan kunci lengkap atau rujukan nilai unik, yang mengendalikan situasi apabila satu kunci adalah awalan kepada kunci yang lain.
Node { prefix, prefixLen, hasValue, value, children }
Leaf { key, value }Panjang awalan adalah eksplisit kerana kunci adalah bait sebarangan, bukan rentetan yang ditamatkan dengan null.
Langkah 2: Sisip dan pisahkan
Bandingkan awalan nod dengan baki kunci. Jika sepadan, teruskan atau kemas kini nilainya. Jika bercanggah, cipta induk yang mengandungi awalan sepunya dan lampirkan nod lama serta daun baharu di bawah bait yang berbeza. Jika kunci baharu berakhir pada awalan sepunya, tetapkan bendera nilai bagi induk tersebut.
Langkah 3: Pilih susun atur adaptif
Node4 dan Node16 mengekalkan tatasusunan kunci dan penunjuk yang padat; carian boleh mengimbasnya atau menggunakan perbandingan vektor. Node48 memetakan kesemua 256 bait yang mungkin kepada 48 slot penunjuk, mengelakkan 256 penunjuk mastautin. Node256 mengindeks secara terus mengikut bait. Naik taraf dengan menyalin anak tanpa kehilangan keadaan awalan atau nilai.
Langkah 4: Carian tepat dan awalan terpanjang
Carian tepat mesti menggunakan setiap bait kunci dan menepati hasValue atau kunci daun yang sama. Carian awalan terpanjang merekodkan calon setiap kali nod mempunyai nilai, kemudian meneruskan melalui bait seterusnya sehingga gagal atau habis dan mengembalikan calon terakhir berserta panjangnya.
Langkah 5: Padam dan kecilkan
Selepas memadamkan nilai, alih keluar nod yang tidak mempunyai anak. Jika nod tanpa nilai mempunyai satu anak, gabungkan awalan dan bait tepinya ke dalam anak tersebut. Turunkan taraf Node256, Node48, Node16 dan Node4 pada ambang bilangan anak yang didokumentasikan. Kekalkan kunci lengkap daun semasa penggabungan.
Langkah 6: Batas tak varian dan kekompleksan
Penggabungan awalan, bait tepi dan daun di sepanjang mana-mana laluan akar-ke-daun mesti menghasilkan semula kunci asal. Nod dalaman tidak boleh mempunyai bait tepi pendua; hasValue bermaksud kunci berakhir tepat di situ. Dengan panjang kunci L, carian ialah O(L); susun atur adaptif mengelakkan peruntukan 256 slot untuk nod yang jarang.
Langkah 7: Uji dan tambah keserentakan
Bandingkan operasi rawak penyisipan, carian, pemadaman dan awalan terpanjang dengan peta rujukan. Sertakan kunci kosong, bait sifar, kunci awalan dan kesemua 256 cabang. Mulakan versi serentak dengan kunci baca-tulis; hanya selepas itu pertimbangkan copy-on-write, epoch atau RCU, kerana penebusgunaan mestilah selamat sebelum penunjuk lock-free didedahkan.
Jawapan model
"Saya menganggap kunci sebagai rentetan bait legap. Nod membawa awalan termampat, nilai penamatan pilihan dan anak. Padanan separa memisahkan induk awalan sepunya; bilangan anak menaik taraf Node4, 16, 48 dan 256, manakala pemadaman menurunkan taraf dan menggabungkan laluan anak tunggal. Carian tepat menggunakan seluruh kunci; carian awalan terpanjang mengingati nod bernilai yang paling hampir.
Setiap laluan mesti membina semula kunci asal. Ujian rawak dibandingkan dengan peta dan merangkumi bait sifar, kunci kosong, kunci awalan dan cabang tumpat. Selepas ketepatan benang tunggal dicapai, gunakan kunci; reka bentuk copy-on-write atau lock-free juga memerlukan epoch atau penebusgunaan selamat yang setara."
Kesilapan biasa
- Menganggap kunci sebagai aksara → kunci binari dan bait sifar gagal → bandingkan panjang bait dan nilai.
- Melupakan nilai dalaman → kunci awalan tidak boleh dipadankan → kekalkan
hasValue. - Memberikan Node48 256 penunjuk → kehilangan penjimatan memori nod jarang → gunakan peta indeks.
- Mengosongkan nilai tanpa menggabungkan → meninggalkan laluan kosong → kecilkan pada ambang.
- Mengabaikan calon leluhur → carian awalan terpanjang terlepas padanan → ingati nod bernilai terakhir.
- Menerbitkan penunjuk mentah tanpa penebusgunaan selamat → pembaca menggunakan memori yang telah dibebaskan → mulakan dengan kunci, kemudian epoch/RCU.
Soalan susulan dan respons
Soalan susulan 1: Mengapa tidak sentiasa menggunakan Node256?
Kebanyakan nod adalah jarang, jadi 256 slot membazirkan memori. Susun atur adaptif mengimbangi kawasan jarang dan tumpat.
Soalan susulan 2: Bagaimana jika satu kunci menjadi awalan kepada kunci yang lain?
Simpan nilai kunci yang lebih pendek pada nod dalaman dan kekalkan anak untuk kunci yang lebih panjang.
Soalan susulan 3: Bilakah anda menggabungkan selepas pemadaman?
Gabungkan nod tanpa nilai yang mempunyai satu anak dengan menggabungkan awalan dan bait tepinya, sambil mengekalkan kunci daun.
Soalan susulan 4: Bagaimanakah anda akan menerbitkan snapshot serentak?
Gunakan copy-on-write untuk akar baharu yang tidak boleh ubah dan tebus guna pepohon lama dengan epoch atau pengiraan rujukan.