Temu Duga Pengekodan: Melaksanakan Radix Tree untuk Penghalaan Awalan

Gesaan dan konteks

Anda diberikan kunci rentetan seperti /api, /api/users, dan /api/users/admin. Laksanakan radix tree di mana setiap sisi menyimpan rentetan tidak kosong dan setiap nod boleh memegang nilai. Sokong insert(key, value), get(key), longestPrefix(key), dan delete(key). Kunci kosong hanya dibenarkan sebagai nilai punca. Penemu duga mahukan struktur data dan penaakulan logik, bukan panggilan perpustakaan.

Perkara yang dinilai oleh penemu duga

• Adakah anda mengekalkan invarian bahawa setiap label sisi bukan punca adalah tidak kosong dan nod beradik mempunyai aksara pertama yang berbeza?
• Bolehkah anda memisahkan sisi pada ketakpadanan pertama tanpa kehilangan sebarang sub-pokok atau nilai?
• Bolehkah anda membezakan carian tepat daripada carian awalan terpanjang?
• Adakah anda memampatkan nod unari tanpa nilai selepas pemadaman dan menyatakan kerumitan sebenar mengikut panjang kunci?

Soalan penjelasan untuk ditanya

Tanya sama ada kunci adalah bait atau titik kod Unicode, sama ada pemadanan peka huruf besar/kecil, sama ada sisipan pendua menggantikan nilai, dan sama ada akses serentak diperlukan. Tanya sama ada longestPrefix mengembalikan kunci yang sepadan, nilai, atau kedua-duanya. Pelaksanaan berorientasikan bait adalah paling mudah dan menjadikan kerumitan bergantung pada bait; penormalan Unicode sepatutnya berada di luar pokok melainkan diminta secara eksplisit. Jika keserentakan diperlukan, tambahkan penyegerakan di sekeliling struktur daripada mendakwa secara senyap bahawa algoritma tersebut selamat untuk bebenang (thread-safe).

Rangka kerja jawapan 30 saat

Setiap nod menyimpan label sisi, nilai pilihan, dan anak yang diindeks mengikut bait pertama mereka. Semasa penyisipan, bandingkan baki kunci dengan label anak. Jika padan sepenuhnya, turun ke bawah; jika padan sebahagian, pisahkan anak kepada nod awalan sepunya dan dua nod akhiran. Carian tepat hanya berjaya apabila keseluruhan kunci digunakan sepenuhnya pada nod bernilai. Carian awalan terpanjang mengingati nilai paling dalam yang dilihat semasa menuruni pokok. Pemadaman mengosongkan nilai dan menggabungkan nod dengan anak tunggalnya apabila nod tersebut tidak mempunyai nilai.

Panduan mendalam langkah demi langkah

1. Nyatakan invarian. Punca tidak mempunyai label sisi. Setiap nod lain mempunyai label yang tidak kosong. Tiada dua anak bagi satu nod bermula dengan bait yang sama. Nod boleh menyimpan nilai walaupun ia juga mempunyai anak, jadi /api dan /api/users wujud bersama.
2. Sisip mengikut awalan sepunya terpanjang. Biarkan p menjadi awalan sepunya antara baki kunci dan label anak. Jika p kosong, pilih anak lain. Jika p sama dengan label anak, gunakan label tersebut dan lakukan rekursi. Jika p lebih pendek, cipta induk baharu berlabel p, alihkan anak lama di bawah akhirannya, kemudian lampirkan akhiran kunci baharu atau ganti nilai apabila kunci berakhir pada pemisahan.
3. Carian. Carian tepat menggunakan satu sisi pada satu masa dan gagal jika berlaku ketakpadanan atau ketiadaan anak. Untuk carian awalan terpanjang, rekod nilai punca dahulu, kemudian rekod setiap nod bernilai yang dicapai sebelum kunci berakhir; kembalikan rekod terakhir.
4. Padam dan mampat. Kosongkan nilai pada sasaran. Jika nod tidak mempunyai nilai dan hanya mempunyai satu anak, cantumkan kedua-dua label dan naikkan pangkat anak-anak kepada anak tersebut. Jika ia mempunyai berbilang anak atau masih mempunyai nilai, kekalkan nod tersebut. Ini memelihara invarian nod beradik.
5. Kerumitan. Dengan pemilihan anak menggunakan peta cincang, setiap operasi membandingkan paling banyak bait kunci input, jadi masa adalah O(k) ditambah overhed peta cincang dan ruang adalah O(jumlah bait kunci yang disimpan). Pemampatan laluan mengurangkan nod unari yang jarang; ia tidak menjadikan kunci yang panjang beroperasi dalam masa malar.
6. Uji kes-kes mencabar. Uji kunci kosong dan satu aksara, menyisip kunci yang merupakan awalan kepada kunci sedia ada, menyisip kunci yang melanjutkan kunci sedia ada, memisahkan di tengah sisi, penggantian pendua, memadam daun, memadam nilai awalan, memadam satu-satunya kunci, dan pertanyaan awalan terpanjang tanpa padanan.

Contoh jawapan berkualiti tinggi

Saya akan mewakili sisi sebagai rentetan bait tidak kosong dan menyimpan anak mengikut bait pertama mereka. Satu-satunya operasi bukan remeh ialah penyisipan: bandingkan label anak dengan baki kunci, dan pisahkan pada ketakpadanan pertama. Pemisahan itu mencipta nod awalan sepunya, mengekalkan akhiran dan sub-pokok lama, serta melampirkan akhiran baharu. Carian mengikut label lengkap; carian awalan terpanjang mengingati nod paling dalam yang memiliki nilai. Pemadaman mengosongkan nilai dan menggabungkan nod tanpa nilai dengan anak tunggalnya. Berikut ialah bentuk pemisahan teras dalam pseudokod 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 kod pengeluaran, saya akan mengendalikan kes di mana newSuffix kosong dengan menyimpan nilai pada parent, dan saya akan memastikan pemadaman hanya bergabung apabila hasValue adalah palsu dan terdapat tepat satu anak. Saya akan menguji invarian selepas setiap mutasi, bukan sekadar mengesahkan bahawa contoh carian berjaya.

Kesilapan lazim

• Memperlakukan radix tree sebagai nod trie satu aksara → pemampatan laluan hilang → simpan label sisi tidak kosong dan bandingkan keseluruhan label.
• Memisahkan sisi tetapi menggugurkan nilai lama atau anaknya → kunci sedia ada hilang → alihkan nod lama di bawah akhirannya sebelum melampirkan akhiran baharu.
• Mengembalikan nilai padanan pertama untuk carian awalan terpanjang → laluan yang lebih khusus terlepas → terus kemas kini calon pada setiap nod bernilai.
• Menggabungkan nod yang masih memiliki nilai → kunci yang lebih pendek terpadam secara tidak sengaja → gabungkan hanya nod unari tanpa nilai.
• Mendakwa carian O(1) → kunci masih perlu dibandingkan → nyatakan O(k) mengikut panjang kunci dan terangkan kos peta anak.

Soalan susulan dan jawapan

Apakah yang berubah jika kunci tidak peka huruf besar/kecil?

Normalkan kunci sebelum penyisipan dan carian menggunakan satu peraturan yang didokumentasikan, seperti huruf kecil ASCII. Jangan normalkan hanya semasa carian; jika tidak, dua ejaan boleh menduduki laluan yang tidak konsisten. Pelipatan huruf (case folding) dan penormalan Unicode harus menjadi dasar berasingan yang ditentukan secara jelas.

Bagaimanakah anda menyokong segmen laluan kad liar (wildcard)?

Tambahkan peraturan keutamaan yang jelas, contohnya sisi statik sebelum sisi parameter sebelum sisi tangkap semua (catch-all). Invarian radix masih mengendalikan awalan harfiah, tetapi pemadanan menjadi carian ke atas jenis sisi, jadi nyatakan bilangan maksimum cabang kad liar dan uji laluan yang samar-samar.

Bolehkah pokok dibuat selamat untuk bacaan dan penulisan serentak?

Gunakan kunci baca-tulis (read-write lock) atau syot kilat salin-semasa-tulis (copy-on-write). Dakwaan bebas kunci (lock-free) memerlukan reka bentuk penebusan memori; hanya menggunakan punca atomik tidak menjadikan pemisahan dan penggabungan setempat selamat. Asingkan invarian algoritma dan dasar penyegerakan.