Temu Duga Pengekodan: Bagaimanakah Anda Melaksanakan Mutable Priority Queue dengan Update dan Remove?

Gesaan dan skop

Laksanakan priority queue dengan add(task, priority), update(task, priority), remove(task), dan pop(). Keutamaan yang sama mesti dikembalikan dalam susunan sisipan; update dan remove mestilah O(log n) terlunas. Terangkan cara entri heap yang lapuk dikendalikan.

Ini menguji ketepatan mutable priority queue, bukan sekadar sama ada anda boleh memanggil API heap. Dokumentasi heapq Python menekankan susunan stabil, tugasan yang tidak boleh dibandingkan, kemas kini keutamaan, dan pembuangan tertangguh sebagai bahagian yang sukar. Reka bentuk lazim menggunakan pembilang untuk penentu seri, peta untuk lokasi, dan pemadaman malas untuk mengekalkan tak varian (invariant) heap.

Perkara yang diuji oleh penemu duga

Pertama, bolehkah anda menulis kunci heap yang lengkap: keutamaan, urutan sisipan, dan tugasan? Kedua, bolehkah kemas kini dan pembuangan mengelak daripada merosakkan heap secara langsung? Ketiga, bolehkah anda mengendalikan tugasan pendua, baris gilir kosong, punca (root) lapuk, dan entri sampah yang berpanjangan?

Soalan untuk dijelaskan sebelum menjawab

Adakah keutamaan berupa nombor atau objek yang boleh dibandingkan? Andaikan integer yang boleh dibandingkan, dengan nilai yang lebih kecil didahulukan.
Adakah ID tugasan unik? Andaikan ya; add pendua sama ada satu kemas kini atau ralat eksplisit.
Adakah susunan stabil diperlukan? Andaikan keutamaan yang sama menggunakan susunan sisipan pertama.
Bolehkah pemadaman malas mengekalkan memori buat sementara waktu? Ya, dengan dasar pembersihan dan pembinaan semula.
Adakah panggilan bersifat serentak (concurrent)? Andaikan satu utas; keserentakan memerlukan kunci luaran atau bekas yang selamat.

Kerangka jawapan 30 saat

"Saya akan menyimpan [priority, sequence, task] dalam min-heap dan memetakan setiap ID tugasan kepada entri sah semasanya. Kemas kini menandakan entri lama telah dialih keluar dan menyisipkan entri baharu dengan urutan baharu; remove juga menandakan entri sebagai lapuk. pop melangkau entri lapuk sehingga ia menemui entri semasa. Urutan memberikan penentu seri yang stabil, peta memberikan carian O(1), operasi heap adalah O(log n), dan pembinaan semula berkala mengehadkan ruang entri malas."

Penelitian mendalam langkah demi langkah

Langkah 1: Tentukan tak varian dan kontrak operasi

Punca mestilah (priority, sequence) terkecil dalam kalangan entri yang sah. Peta menyimpan entri semasa untuk setiap tugasan. Sesuatu tugasan mempunyai paling banyak satu entri yang sah; entri lapuk mungkin kekal dalam heap tetapi tidak boleh dikembalikan sama sekali. Tentukan sama ada pop yang kosong menimbulkan ralat atau mengembalikan nilai kosong.

Langkah 2: Pilih entri heap yang boleh dibandingkan

Gunakan [priority, sequence, task]. sequence yang monotonik menjadikan keutamaan yang sama boleh dibandingkan tanpa membandingkan objek tugasan. Jika arah keutamaan perniagaan diterbalikkan, nafikan nilainya atau balut pembanding secara konsisten; jangan campurkan peraturan antara operasi.

Langkah 3: Laksanakan add dan update

add pertama memperuntukkan urutan dan menulis entri pada kedua-dua peta dan heap. update mengesahkan kewujudan, menandakan entri lama REMOVED, menyisipkan entri baharu, dan menggantikan penuding peta. Tiada carian heap atau anjakan manual (sift), jadi operasi kekal 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: Laksanakan remove dengan pemadaman malas

remove memadamkan tugasan daripada peta dan menggantikan medan tugasan dalam entri heap-nya dengan REMOVED. Mengalih keluar daripada tatasusunan secara terus akan merosakkan heap dan memerlukan pembaikan tambahan. Pemadaman malas menyentuh satu entri yang diketahui bagi setiap mutasi, dengan kos sampah sementara.

Langkah 5: Buat pop melangkau entri lapuk

Lakukan pop pada punca berulang kali. Jika ia ditandakan REMOVED, teruskan. Jika peta tidak menunjuk kepada entri tepat yang di-pop, ia telah digantikan oleh kemas kini, jadi langkau ia. Bagi entri yang sah, padamkan kunci peta dan kembalikan tugasan. Timbulkan ralat baris gilir kosong hanya selepas heap kehabisan entri.

Langkah 6: Buktikan kekompleksan dan batas terlunas

add, update, dan remove melakukan satu sisipan heap atau penandaan masa malar, memberikan penandaan O(log n) atau O(1). Setiap entri lapuk di-pop paling banyak sekali, jadi kerja yang dilangkau dilunaskan kepada kemas kini atau pengalihan keluar yang menciptanya. Jika kemas kini berterusan tanpa sebarang pop, ruang akan berkembang dan pembinaan semula diperlukan.

Langkah 7: Reka bentuk pembinaan semula dan kawalan ruang

Apabila panjang heap melebihi gandaan tetap entri sah, seperti 2x, atau entri lapuk melepasi ambang, kekalkan entri semasa daripada peta dan bina semula heap. Pembinaan semula menelan kos O(n), tetapi pencetus frekuensi rendah memastikan kos terlunas kekal terbatas. Dengan had tugasan yang diketahui, pembersihan juga boleh dijalankan selepas kelompok kemas kini.

Langkah 8: Rangkumi ujian sempadan

Uji baris gilir kosong, keutamaan sama yang stabil, kemas kini berulang, remove kemudian pop, entri lapuk yang dikemas kini sampai ke punca, semua entri menjadi lapuk, objek tugasan yang tidak boleh dibandingkan, dan hasil yang sama sebelum dan selepas pembinaan semula. Uji pembezaan operasi rawak terhadap model ringkas kamus serta senarai terisih.

Pertukaran dan sempadan

Pertukaran 1: Pemadaman malas atau indexed heap

Pemadaman malas adalah pendek dan berisiko rendah untuk pelaksanaan umum. Indexed heap mengalih keluar serta-merta dan mengawal ruang, tetapi mengekalkan kedudukan semasa pertukaran adalah lebih cenderung kepada pepijat. Pilih indexed heap hanya apabila kadar pemadaman dan had memori mewajarkannya.

Pertukaran 2: Bolehkah urutan melimpah (overflow)?

Integer lebar tetap boleh membalut (wrap) dan memecahkan susunan yang stabil. Gunakan integer tidak terikat atau nomborkan semula semua entri aktif semasa pembinaan semula yang selamat. Jangan sekali-kali menetapkan semula pembilang selagi entri aktif masih bergantung pada nilai lama.

Pertukaran 3: Ralat atau nilai kosong

Pustaka lazimnya membangkitkan pengecualian baris gilir kosong yang jelas, membolehkan pemanggil membezakan "tiada tugasan" daripada tugasan yang nilainya null. Jika API mengembalikan nilai kosong, dokumentasikan kekaburan tersebut dan jangan benarkan nilai tugasan yang bercanggah.

Latih tubi kegagalan dan pelan evolusi

Latih tubi 1: Kemas kini satu tugasan berulang kali

Kemas kini satu tugasan sebanyak 10,000 kali, kemudian lakukan pop dan sahkan keutamaan terkini dikembalikan tepat sekali. Perhatikan pertumbuhan entri lapuk, cetuskan pembinaan semula, dan semak semula tak varian heap.

Latih tubi 2: Operasi bercampur rawak

Hasilkan operasi rawak add, update, remove, dan pop serta bandingkan dengan model kamus campur senarai terisih. Beri tumpuan pada susunan urutan keutamaan sama dan pastikan entri lama yang dikemas kini tidak bocor.

Latih tubi 3: Ralat dan had sumber

Panggil update/remove untuk tugasan yang tiada, pop baris gilir kosong, dan cetuskan pembinaan semula pada ambang memori. Sahkan jenis ralat yang stabil, tiada tugasan yang hilang, dan tiada keadaan terbina separa terdedah kepada pemanggil.

Kesilapan lazim dan tindakan susulan

Kesilapan 1: Menyimpan hanya keutamaan dan tugasan

Objek tugasan mungkin tidak boleh dibandingkan, menyebabkan perbandingan keutamaan sama gagal. Tambah urutan yang stabil atau pembalut yang tidak boleh dibandingkan.

Kesilapan 2: Mengubah suai entri heap di tempat asal (in place) untuk kemas kini

Entri tersebut mungkin tidak lagi berada di kedudukan yang betul, lalu melanggar tak varian heap. Tandakan entri lama sebagai lapuk dan sisipkan entri baharu.

Kesilapan 3: Memanggil array remove untuk pemadaman

Cariannya adalah O(n), diikuti oleh pembaikan heap. Gunakan peta untuk mencari entri dan menandakannya sebagai lapuk.

Kesilapan 4: Hanya menyemak medan tugasan dalam pop

Entri lama yang dikemas kini masih boleh membawa ID tugasan yang sama. Sahkan bahawa objek yang di-pop ialah entri peta semasa.

Kesilapan 5: Mengabaikan ruang entri lapuk

Pemadaman malas masih menggunakan memori. Tetapkan ambang pembinaan semula dan pantau panjang heap, kiraan entri sah, dan nisbah lapuk.

Kesilapan 6: Membiarkan arah keutamaan secara tersirat

Min-heap mengembalikan nilai terkecil dahulu. Jika nombor yang lebih besar bermaksud keutamaan perniagaan yang lebih tinggi, tentukan penukaran dalam kontrak supaya add dan pop bersetuju.