Wawancara Coding: Bagaimana Anda Mengimplementasikan Randomized Meldable Heap?

Petunjuk dan Konteks

Anda sedang mengimplementasikan min-priority queue yang dapat digabungkan (meldable) untuk penjadwal tugas (task scheduler). Pemanggil sering kali menggabungkan dua antrean, kemudian memasukkan pekerjaan dan menghapus prioritas terkecil. Implementasikan meld, insert, find-min, dan extract-min, serta nyatakan pilihan Anda terkait pengacakan, heap kosong, kunci duplikat, dan kepemilikan node.

Randomized meldable heap merepresentasikan urutan heap sebagai pohon biner tanpa metadata peringkat seperti leftist rank. Pada setiap penggabungan, struktur ini memilih cabang rekursif kiri atau kanan secara acak. Wawancara ini menguji invarian, asumsi probabilitas, dan kemampuan pengujian (testability).

Apa yang Dievaluasi oleh Pewawancara

Cakup invarian root minimum, semantik pertukaran dan konsumsi dari meld, batas bit acak, kunci duplikat, kepemilikan, kedalaman rekursi, destruksi, dan perbedaan antara batas ekspektasi dan kasus terburuk. Bandingkan binary heap, leftist heap, dan pairing heap sesuai dengan beban kerja.

Pertanyaan Klarifikasi yang Perlu Diajukan

Apakah meld mengonsumsi heap masukannya, atau kedua heap asli harus tetap dapat digunakan?
Bisakah sumber acak diinjeksi sehingga kegagalan dapat diputar ulang (replayable)?
Berapa batas node dan anggaran stack rekursi?
Apakah handle yang stabil, penghapusan arbitrer, atau decrease-key diperlukan?
Apakah tujuannya adalah implementasi pembelajaran, throughput produksi, atau batas kasus terburuk yang ketat?

Kerangka Jawaban 30 Detik

“Setiap node menyimpan kunci, nilai, dan dua pointer anak. meld(a,b) menangani pohon kosong, mempertahankan root yang lebih kecil, lalu menggabungkan pohon lainnya secara acak ke anak kiri atau kanan. insert menggabungkan singleton dengan root, dan extract-min menggabungkan anak-anak dari root yang dihapus. Root tetap minimal dan operasi biasanya memerlukan waktu logaritmik ekspektasi, tetapi kedalaman rekursi dan seed acak memerlukan pengujian dan batasan eksplisit.”

Jawaban Mendalam, Langkah demi Langkah

Langkah 1: Definisikan Node dan Kepemilikan

Simpan key, value, left, dan right di setiap node. Heap menyimpan root dan jumlah nodenya. Dengan implementasi mutable, meld menyambungkan kembali root masukan, sehingga API harus menyatakan apakah masukan dikonsumsi. Implementasi persisten menyalin jalur dan oleh karena itu mengubah biaya waktu dan ruang.

text

meld(a, b):
  if a is empty: return b
  if b is empty: return a
  if b.key < a.key: swap(a, b)
  if randomBit() == 0:
    a.left = meld(a.left, b)
  else:
    a.right = meld(a.right, b)
  return a

Langkah 2: Pertahankan Invarian Meld

Bandingkan root terlebih dahulu dan pertahankan kunci yang lebih kecil sebagai root. Kunci yang sama dapat menggunakan aturan pemutus seri (tie rule) tetap atau aturan acak, tetapi urutan heap harus tetap valid. Setelah rekursi kembali, setiap kunci pada anak yang digabungkan setidaknya bernilai sebesar root saat ini, sehingga invarian tetap berlaku di sepanjang jalur.

Jangan memasang satu node ke dua induk. meld yang mutable harus melacak kepemilikan; build debug dapat memeriksa hitungan dan siklus. Implementasi persisten tidak dapat memutasi subtree yang dibagikan.

Langkah 3: Implementasikan Insert dan Find-Min

insert membuat sebuah singleton dan menggabungkannya dengan root saat ini, lalu menambah jumlah node. find-min membaca root; heap kosong mengikuti kontrak antarmuka dengan mengembalikan hasil kosong atau kesalahan. Kunci duplikat tetap disimpan sebagai entri terpisah.

Sumber acak global membuat pengujian sulit diputar ulang. Suntikkan sumber acak dan gunakan seed tetap dalam pengujian; produksi tetap membutuhkan implementasi bit acak yang tidak bias dan independen.

Langkah 4: Implementasikan Extract-Min

Setelah menghapus root, gabungkan subtree kiri dan kanannya untuk membentuk root baru. Lepaskan kedua pointer sebelum mengurangi jumlah node; jika heap memiliki memori, lepaskan root lama paling akhir. Ketika masukan dikonsumsi, batalkan validitas handle ke root yang dihapus.

Jika versi lama harus tetap dapat digunakan, gunakan penyalinan jalur (path copying) persisten daripada memutasi node yang dibagikan. Nyatakan hal ini pada batas antarmuka karena aliasing dapat merusak data secara diam-diam.

Langkah 5: Nyatakan Batas Kompleksitas

Untuk randomized meldable heap, meld, insert, dan extract-min umumnya dianalisis sebagai logaritmik ekspektasi atau logaritmik probabilitas tinggi di bawah model acak yang dinyatakan. find-min membutuhkan waktu konstan, dan ruang bersifat linier terhadap jumlah node.

Jangan mengubah batas ekspektasi menjadi klaim kasus terburuk per operasi. Urutan acak yang tidak menguntungkan dapat menghasilkan pohon yang dalam. Kode produksi harus membatasi rekursi, menggunakan stack eksplisit bila diperlukan, dan memvalidasi distribusi dengan benchmark dan pengujian acak.

Langkah 6: Uji terhadap Referensi

Lakukan differential-test terhadap priority queue standar dengan heap kosong, kunci duplikat, penggabungan bergantian, ekstraksi berulang, seed tetap, dan kasus ekstrem kedalaman. Setelah setiap operasi, periksa root minimum, jumlah node, asiklisitas, dan aturan kepemilikan.

Tidak seperti pairing heap, desain ini menggunakan pohon biner dan cabang acak, sehingga tidak memerlukan daftar saudara (sibling lists), penggabungan dua lintasan, atau pemotongan handle. Tidak seperti leftist heap, struktur ini menghilangkan metadata peringkat dan menggunakan analisis probabilistik. Diskusikan lokalitas cache, mutasi, dan persyaratan pembuktian secara bersamaan.

Contoh Jawaban Berkualitas Tinggi

Saya mempertahankan kunci terkecil di root. meld mengembalikan pohon yang tidak kosong, menukar root sehingga a lebih kecil, dan secara acak menggabungkan b ke dalam a.left atau a.right. Baik insert maupun extract-min menggunakan kembali meld, sedangkan find-min membaca root. Pertama-tama saya mengklarifikasi apakah meld mengonsumsi masukan; kemudian saya menginjeksi sumber acak deterministik untuk pengujian diferensial, memeriksa siklus, hitungan, kepemilikan, dan urutan root. Saya menjelaskan batas logaritmik ekspektasi atau probabilitas tinggi di bawah model acak dan menangani kedalaman rekursi secara terpisah.

Kesalahan Umum

Mengacak sebelum membandingkan root → root hasil mungkin terlalu besar → tukar root terlebih dahulu, baru pilih anak.
Menggunakan kembali heap mutable lama setelah meld → satu node memiliki dua induk → nyatakan konsumsi atau implementasikan persistensi.
Menyebut batas ekspektasi sebagai O(log n) kasus terburuk → asumsi probabilitas hilang → sebutkan model acak dan kualifikasi probabilitas tinggi.
Menggunakan sumber acak yang tidak dapat diinjeksi → kegagalan tidak dapat diputar ulang → injeksikan dan kunci seed dalam pengujian.
Mengabaikan kedalaman rekursi → pohon yang ekstrem dapat menghabiskan call stack → gunakan stack eksplisit, pantau kedalaman, atau dokumentasikan batasan.

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan Lanjutan 1: Bagaimana Anda membuat pengujian menjadi deterministik?

Jadikan generator bit acak sebagai dependensi heap. Pengujian menyediakan urutan atau seed tetap, sementara produksi menggunakan instans independen sehingga status acak global tidak menggabungkan kasus uji.

Pertanyaan Lanjutan 2: Bagaimana jika meld harus mempertahankan kedua masukan?

Gunakan implementasi persisten dengan penyalinan jalur dan subtree yang tidak tersentuh dibagikan. Perbarui batas ruang dan rencana reklamasi memori; jangan mengklaim ruang tambahan konstan untuk penggabungan in-place.

Pertanyaan Lanjutan 3: Bagaimana jika kedua heap mereferensikan node yang sama?

API mutable harus menolak pembagian lintas-heap dan mencatat kepemilikan dalam build debug. API persisten dapat berbagi struktur hanya ketika node bersifat immutable. Kembalikan kesalahan kepemilikan daripada memperbaiki alias secara diam-diam.

Pertanyaan Lanjutan 4: Mengapa tidak menggunakan pairing heap?

Pairing heap cocok untuk beban kerja yang membutuhkan decrease-key, tetapi mempertahankan daftar anak multi-cabang dan restrukturisasi penghapusan. Randomized meldable heap memiliki meld biner yang lebih pendek untuk beban kerja yang memerlukan penggabungan, penyisipan, dan penghapusan minimum sambil menerima jaminan probabilistik.