Wawancara Koding: Bagaimana Anda Mengimplementasikan Mutable Priority Queue dengan Update dan Remove?

Petunjuk dan ruang lingkup

Implementasikan priority queue dengan add(task, priority), update(task, priority), remove(task), dan pop(). Prioritas yang sama harus dikembalikan dalam urutan penyisipan; update dan remove harus diamortisasi O(log n). Jelaskan bagaimana entri heap yang usang ditangani.

Ini menguji kebenaran dari mutable priority queue, bukan hanya apakah Anda dapat memanggil heap API. Dokumentasi heapq Python menyoroti pengurutan yang stabil, task yang tidak dapat dibandingkan, pembaruan prioritas, dan penghapusan tertunda sebagai bagian-bagian yang sulit. Desain yang umum menggunakan penghitung untuk seri (ties), map untuk lokasi, dan lazy deletion untuk mempertahankan invarian heap.

Apa yang sedang diuji oleh pewawancara

Pertama, dapatkah Anda menulis heap key yang lengkap: prioritas, urutan penyisipan (sequence), dan task? Kedua, dapatkah pembaruan dan penghapusan menghindari perusakan heap secara langsung? Ketiga, dapatkah Anda menangani task duplikat, antrean kosong, root yang usang, dan entri sampah yang berumur panjang?

Pertanyaan untuk diklarifikasi sebelum menjawab

Apakah prioritas berupa angka atau objek yang dapat dibandingkan? Asumsikan integer yang dapat dibandingkan, dengan nilai terkecil terlebih dahulu.
Apakah ID task unik? Asumsikan ya; add duplikat adalah pembaruan atau error eksplisit.
Apakah pengurutan yang stabil diperlukan? Asumsikan prioritas yang sama menggunakan urutan penyisipan pertama.
Bolehkah lazy deletion mempertahankan memori untuk sementara? Ya, dengan kebijakan pembersihan dan pembangunan ulang (rebuild).
Apakah pemanggilan bersifat konkuren? Asumsikan satu thread; konkurensi membutuhkan kunci eksternal atau wadah yang aman.

Kerangka jawaban 30 detik

"Saya akan menyimpan [priority, sequence, task] dalam min-heap dan memetakan setiap ID task ke entri validnya saat ini. Pembaruan menandai entri lama telah dihapus dan menyisipkan entri baru dengan sequence baru; remove juga menandai entri sebagai usang (stale). pop melompati entri usang sampai menemukan entri yang valid saat ini. Sequence memberikan kestabilan saat seri, map memberikan pencarian O(1), operasi heap adalah O(log n), dan pembangunan ulang berkala membatasi ruang entri lazy."

Penyelaman mendalam langkah demi langkah

Langkah 1: Tentukan invarian dan kontrak operasi

Root harus berupa (priority, sequence) terkecil di antara entri yang valid. Map menyimpan entri saat ini untuk setiap task. Sebuah task memiliki paling banyak satu entri valid; entri usang dapat tetap berada di heap tetapi tidak boleh dikembalikan. Tentukan apakah pop yang kosong memunculkan error atau mengembalikan nilai kosong.

Langkah 2: Pilih entri heap yang dapat dibandingkan

Gunakan [priority, sequence, task]. sequence yang monoton membuat prioritas yang sama dapat dibandingkan tanpa membandingkan objek task. Jika arah prioritas bisnis dibalik, negasikan nilainya atau bungkus pembanding secara konsisten; jangan mencampur aturan antar operasi.

Langkah 3: Implementasikan add dan update

add pertama mengalokasikan sequence dan menulis entri ke map dan heap. update memverifikasi keberadaan, menandai entri lama sebagai REMOVED, menyisipkan entri baru, dan mengganti pointer map. Tidak ada pencarian heap atau pergeseran manual (sift), sehingga operasi tetap O(log n).

text

add(task, priority):
    if task is active: mark old entry removed
    entry = [priority, next(sequence), task]
    current[task] = entry
    heappush(heap, entry)

Langkah 4: Implementasikan remove dengan lazy deletion

remove menghapus task dari map dan mengganti field task di entri heap-nya dengan REMOVED. Menghapus dari array secara langsung akan merusak heap dan memerlukan perbaikan ekstra. Lazy deletion menyentuh satu entri yang diketahui per mutasi, dengan konsekuensi sampah sementara.

Langkah 5: Buat pop melompati entri usang

Lakukan pop pada root secara berulang. Jika ditandai REMOVED, lanjutkan. Jika map tidak menunjuk ke entri persis yang sedang di-pop, itu telah digantikan oleh pembaruan, jadi lewati. Untuk entri yang valid, hapus key map dan kembalikan task. Munculkan error antrean kosong hanya setelah heap habis.

Langkah 6: Buktikan kompleksitas dan batas amortisasi

add, update, dan remove melakukan satu penyisipan heap atau penandaan waktu konstan, menghasilkan O(log n) atau penandaan O(1). Setiap entri usang di-pop paling banyak satu kali, sehingga pekerjaan yang dilewati diamortisasi ke pembaruan atau penghapusan yang membuatnya. Jika pembaruan berlanjut tanpa pop, ruang memori tumbuh dan pembangunan ulang diperlukan.

Langkah 7: Rancang pembangunan ulang dan kontrol ruang memori

Ketika panjang heap melebihi kelipatan tetap dari entri valid, seperti 2x, atau entri usang melewati ambang batas, pertahankan entri saat ini dari map dan bangun ulang heap. Pembangunan ulang memakan biaya O(n), tetapi pemicu frekuensi rendah menjaga biaya amortisasi tetap terbatas. Dengan batas task yang diketahui, pembersihan juga dapat berjalan setelah sekumpulan pembaruan batch.

Langkah 8: Cakup pengujian batas

Uji antrean kosong, prioritas sama yang stabil, pembaruan berulang, remove kemudian pop, entri lama yang diperbarui mencapai root, semua entri menjadi usang, objek task yang tidak dapat dibandingkan, dan hasil identik sebelum dan sesudah pembangunan ulang. Lakukan differential testing untuk operasi acak terhadap model sederhana dictionary plus sorted list.

Pertukaran dan batasan

Pertukaran 1: Lazy deletion atau indexed heap

Lazy deletion singkat dan berisiko rendah untuk implementasi umum. Indexed heap menghapus secara langsung dan mengontrol ruang, tetapi mempertahankan posisi selama swap lebih rentan bug. Pilih indexed heap hanya jika rasio penghapusan dan batas memori membenarkannya.

Pertukaran 2: Bisakah sequence meluap (overflow)?

Integer lebar tetap dapat mengalami overflow dan merusak pengurutan yang stabil. Gunakan unbounded integer atau beri nomor ulang semua entri aktif selama pembangunan ulang yang aman. Jangan pernah me-reset counter saat entri aktif masih bergantung pada nilai lama.

Pertukaran 3: Error atau nilai kosong

Library umumnya memunculkan exception antrean kosong yang jelas, memungkinkan pemanggil membedakan "tidak ada task" dari task yang nilainya null. Jika suatu API mengembalikan nilai kosong, dokumentasikan ambiguitas tersebut dan larang nilai task yang berkonflik.

Simulasi kegagalan dan rencana evolusi

Simulasi 1: Perbarui satu task berulang kali

Perbarui satu task sebanyak 10.000 kali, lalu lakukan pop dan verifikasi bahwa prioritas terbaru dikembalikan tepat satu kali. Amati pertumbuhan entri usang, picu pembangunan ulang, dan periksa kembali invarian heap.

Simulasi 2: Operasi campuran acak

Hasilkan operasi add, update, remove, dan pop acak dan bandingkan dengan model dictionary plus sorted list. Fokus pada urutan sequence prioritas yang sama dan pastikan entri lama yang diperbarui tidak pernah bocor.

Simulasi 3: Error dan batas sumber daya

Panggil update/remove untuk task yang tidak ada, pop antrean kosong, dan picu pembangunan ulang pada ambang batas memori. Verifikasi tipe error yang stabil, tidak ada task yang hilang, dan tidak ada state yang dibangun ulang sebagian terekspos ke pemanggil.

Kesalahan umum dan tindak lanjut

Kesalahan 1: Hanya menyimpan prioritas dan task

Objek task mungkin tidak dapat dibandingkan, menyebabkan perbandingan prioritas yang sama gagal. Tambahkan sequence yang stabil atau pembungkus yang tidak dapat dibandingkan.

Kesalahan 2: Mengubah entri heap di tempat (in place) untuk update

Entri tersebut mungkin tidak lagi berada di posisi yang benar, melanggar invarian heap. Tandai entri lama sebagai usang dan sisipkan entri baru.

Kesalahan 3: Memanggil array remove untuk penghapusan

Pencariannya adalah O(n), diikuti oleh perbaikan heap. Gunakan map untuk menemukan entri dan menandainya sebagai usang.

Kesalahan 4: Hanya memeriksa field task dalam pop

Entri lama yang diperbarui masih dapat membawa ID task yang sama. Konfirmasikan bahwa objek yang di-pop adalah entri map saat ini.

Kesalahan 5: Mengabaikan ruang entri usang

Lazy deletion tetap mengonsumsi memori. Tetapkan ambang batas pembangunan ulang dan pantau panjang heap, jumlah entri valid, dan rasio entri usang.

Kesalahan 6: Membiarkan arah prioritas implisit

Min-heap mengembalikan nilai terkecil terlebih dahulu. Jika angka yang lebih besar berarti prioritas bisnis lebih tinggi, tentukan konversi dalam kontrak sehingga add dan pop selaras.