Wawancara coding: Mengimplementasikan radix heap integer monoton

Permintaan dan kasus penggunaan

Radix heap adalah struktur integer untuk antrean prioritas monoton, berguna dalam algoritma seperti Dijkstra di mana kunci yang diekstraksi bersifat tidak menurun. Struktur ini menggunakan kunci terakhir yang diekstraksi sebagai batas dan mengelompokkan ke dalam ember berdasarkan bit berbeda tertinggi.

Apa yang dievaluasi pewawancara

• Apakah kunci yang dimasukkan dibatasi oleh kunci yang terakhir diekstraksi.
• Apakah bit berbeda tertinggi dan rentang ember sudah benar.
• Apakah ember tidak kosong terkecil diredistribusikan dengan basis baru.
• Apakah invarian ember dan kunci minimum tetap terjaga.
• Apakah antrean kosong, overflow, dan kunci mundur (backward) ditangani.
• Apakah redistribusi dan kompleksitas teramortisasi dijelaskan secara jujur.

Klarifikasi sebelum menjawab

• Apakah kunci merupakan integer unsigned dengan lebar tetap atau presisi arbitrer?
• Bolehkah kunci yang dimasukkan lebih kecil dari kunci terakhir yang diekstraksi?
• Apakah payload dengan kunci yang sama harus stabil?
• Apakah hanya pop-min yang diperlukan, atau juga decrease-key dan penghapusan?
• Apa yang harus dikembalikan oleh pop pada kondisi kosong dan overflow?
• Apakah kejelasan, faktor konstanta rendah, atau batasan asimtotik yang menjadi prioritas?

Kerangka jawaban 30 detik

"Saya mempertahankan last, kunci yang paling baru diekstraksi, dan ember W+1. Kunci yang sama dengan last masuk ke ember 0; jika tidak, embernya adalah bit_length(key XOR last). Jika ember 0 kosong, saya mencari ember tidak kosong terkecil, memindai kunci minimumnya sebagai last baru, meredistribusikan ember tersebut, dan melakukan pop dari ember 0. Kunci di bawah last akan ditolak."

Pembahasan mendalam langkah demi langkah

Langkah 1: Nyatakan invarian. last tidak pernah menurun, setiap kunci yang tertunda memenuhi key >= last, dan ember i berisi kunci-kunci yang bit berbeda tertingginya dari last adalah i.

Langkah 2: Hitung ember. Indeks bernilai 0 ketika key == last; jika tidak, gunakan bit_length(key XOR last). Kunci sebesar W-bit membutuhkan ember W+1.

Langkah 3: Implementasikan push. Periksa non-negativitas, lebar bit, dan key >= last, lalu tempatkan (key, value) di embernya; kunci yang sama dapat berdampingan.

Langkah 4: Implementasikan pop. Kembalikan dari ember 0 jika tidak kosong. Jika kosong, cari ember tidak kosong terendah, pindai kunci minimumnya, dan tetapkan ke last.

Langkah 5: Redistribusikan. Kosongkan ember tersebut dan hitung ulang indeks setiap item terhadap last yang baru; indeks akan menurun dan setidaknya satu item mencapai ember 0.

Langkah 6: Tangani batas. Kembalikan hasil kosong yang telah ditentukan; tolak kunci di luar lebar bit atau di bawah last untuk menghindari perilaku XOR dan indeks yang tidak terdefinisi.

Langkah 7: Nyatakan kompleksitas. Setiap item diredistribusikan dalam jumlah kali yang dibatasi oleh ukuran kata W; biaya teramortisasi umum adalah O(W), ruangnya adalah O(n + W), dan struktur ini tidak selalu lebih cepat daripada binary heap secara universal.

Model jawaban berkualitas tinggi

"Saya menggunakan kunci unsigned 64-bit dan 65 ember. last dimulai dari nol; kunci di bawah last ditolak, jika tidak bit_length(key XOR last) akan memilih embernya. pop mengambil dari ember 0, atau menemukan ember tidak kosong terendah, memindai kunci minimumnya ke dalam last, dan meredistribusikan. Kunci yang sama mempertahankan payload terpisah. Pop pada kondisi kosong mengembalikan nilai kosong, dan overflow atau kunci mundur akan gagal. Setiap item hanya diredistribusikan sebanyak jumlah yang dibatasi ukuran kata, dengan ruang untuk item ditambah ember."

Kesalahan umum

• Mengizinkan kunci mundur → invarian ember gagal → tolak key < last.
• Menggunakan log2(key) untuk ember → basis saat ini diabaikan → gunakan key XOR last.
• Membiarkan last tidak berubah setelah redistribusi → ekstraksi bisa salah → pindai nilai minimum terlebih dahulu.
• Mengambil item pertama dalam ember → item tersebut mungkin bukan nilai minimum → lakukan pemindaian untuk kunci minimum.
• Mengklaim setiap operasi adalah O(1) → ukuran kata dan redistribusi terabaikan → nyatakan asumsi W dan amortisasi.

Pertanyaan lanjutan dan tanggapan

Pertanyaan lanjutan 1: Mengapa struktur ini cocok untuk Dijkstra?

Jarak yang diekstraksi bersifat tidak menurun, dan jarak kandidat baru tidak berada di bawah nilai minimum saat ini, sehingga memenuhi persyaratan kunci monoton.

Pertanyaan lanjutan 2: Bagaimana jika diperlukan decrease-key arbitrer?

Radix heap tidak cocok untuk kunci mundur. Gunakan binary heap atau pairing heap, atau pertahankan versi dan buang entri usang secara lazy.

Pertanyaan lanjutan 3: Mengapa ember 0 dapat di-pop secara langsung?

Setiap kunci di ember 0 bernilai sama dengan last, jadi semuanya merupakan kunci minimum saat ini.

Pertanyaan lanjutan 4: Mengapa indeks yang diredistribusikan menurun?

last yang baru adalah nilai minimum ember; bit berbeda tertinggi dari setiap item lainnya tidak lebih besar dari indeks ember lama, dan setidaknya satu item mencapai ember 0.

Pertanyaan lanjutan 5: Bagaimana cara menjaga kunci yang sama tetap stabil?

Tambahkan nomor urut monoton ke payload dan pilih (key, sequence) di ember 0; selebihnya stabilitas bersifat opsional.

Pertanyaan lanjutan 6: Bagaimana dengan kunci negatif?

Petakan ke dalam ruang terurut unsigned atau tentukan hanya untuk kunci non-negatif. XOR bertanda tanpa definisi pengurutan tidaklah aman.

Pertanyaan lanjutan 7: Kapan binary heap lebih baik?

Gunakan binary heap ketika kunci bukan integer monoton, ukuran kata besar, pembaruan bersifat kompleks, atau kesederhanaan dan keumuman lebih penting daripada batasan khusus.