Temuduga Pengekodan: Bagaimana Anda Mereka Bentuk Max Stack dengan popMax?

Masalah dan konteks

Laksanakan MaxStack: push(x) menambah item, pop() menyingkirkan dan mengembalikan elemen teratas, top() membaca elemen teratas, peekMax() membaca nilai maksimum, dan popMax() menyingkirkan dan mengembalikan nilai maksimum yang paling hampir dengan bahagian atas. Nilai maksimum yang berulang menggunakan pemutus seri keluar-dahulu-masuk-terakhir (LIFO); tingkah laku tindanan kosong mestilah ralat eksplisit atau hasil kosong.

Masalah LeetCode awam dan rekod soalan temuduga terkini menggunakan antara muka ini. Ia berbeza daripada tindanan minimum awalan: popMax mesti mencari nod dalaman dan memulihkan susunan tindanan yang selebihnya.

Perkara yang diuji oleh penemuduga

• Sama ada anda menetapkan pemutus seri nilai maksimum pendua dan kontrak tindanan kosong terlebih dahulu.
• Sama ada anda boleh menerangkan sebab satu pemboleh ubah currentMax tidak dapat memulihkan nilai maksimum seterusnya selepas pemadaman.
• Sama ada anda memisahkan susunan tindanan daripada susunan nilai dan menyingkirkan nod yang sama daripada kedua-dua indeks.
• Sama ada anda membezakan reka bentuk tindanan bantuan O(1) yang dilunaskan daripada reka bentuk indeks tertib O(log n).

Penjelasan sebelum mengekod

1. Adakah popMax mesti berupa O(1), dilunaskan O(1), atau bolehkah ia berupa O(log n)? Ini menentukan struktur data.
2. Untuk nilai maksimum pendua, adakah item yang paling hampir dengan bahagian atas mesti disingkirkan, atau sebarang nilai maksimum boleh diterima? Peraturan ini mengubah carian indeks.
3. Adakah lelaran stabil, panggilan serentak, atau ketekalan (persistence) diperlukan? Ia mengubah jangka hayat nod dan penguncian.
4. Adakah nilai merupakan objek yang boleh dibandingkan atau integer terikat? Integer terikat membenarkan baldi (buckets); objek generik biasanya memerlukan indeks perbandingan.

Jawapan 30 saat

“Saya membungkus setiap nilai dalam nod dengan nombor jujukan yang meningkat secara monoton. Senarai berpaut ganda dua mengekalkan susunan tindanan; indeks tertib menyusun mengikut (value, sequence), jadi entri terakhirnya ialah nilai maksimum yang paling hampir dengan bahagian atas. top membaca ekor senarai, peekMax membaca ekor indeks, dan popMax mengambil nod tersebut dan memutuskan pautannya melalui penunjuk senarainya. Dengan indeks pokok seimbang, push, pop, peekMax, dan popMax ialah O(log n), manakala top ialah O(1). Jika hanya operasi teratas dan peekMax memerlukan masa malar, tindanan max bantuan adalah lebih mudah, tetapi popMax tidak boleh kekal sebagai O(1) secara jujur.”

Panduan mendalam langkah demi langkah

Langkah 1: Asingkan susunan tindanan daripada susunan tertib.

Setiap nod menyimpan value, sequence yang meningkat secara monoton, prev, dan next. Ekor senarai ialah bahagian atas tindanan. Kunci tertib ialah (value, sequence); untuk nilai yang sama, jujukan yang lebih besar disusun kemudian, menjadikan ekor indeks sebagai nilai maksimum yang paling hampir dengan bahagian atas.

Langkah 2: Pilih indeks tertib yang boleh dipadam.

Gunakan pokok seimbang yang menyokong pendua, TreeMap bersama set nod tertib, atau indeks dua peringkat daripada nilai kepada ID jujukan tertib. Satu currentMax sahaja tidak mencukupi: selepas memadamkannya, nilai maksimum seterusnya dan nodnya mesti dicari.

Langkah 3: Pastikan kesemua lima operasi disegerakkan.

• push: cipta nod, tambahkan pada senarai, dan masukkan ke dalam indeks tertib.
• pop: ambil ekor senarai, keluarkan nod tersebut daripada indeks tertib, kemudian putuskan pautannya.
• top: kembalikan nilai ekor senarai.
• peekMax: kembalikan nilai ekor indeks tertib.
• popMax: ambil ekor indeks tertib, putuskan pautannya melalui penunjuk senarainya, kemudian keluarkannya daripada indeks.

Pseudokod menunjukkan invarian utama; API pokok konkrit adalah khusus untuk setiap bahasa:

node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value

Langkah 4: Kerumitan dan alternatif yang lebih mudah.

Dengan pokok seimbang, top ialah O(1) dan operasi indeks lain ialah O(log n); ruang ialah O(n). Jika popMax O(n) yang dilunaskan boleh diterima, tindanan utama serta tindanan max awalan merekodkan nilai maksimum pada setiap kedalaman. Itu lebih mudah, tetapi ia tidak sesuai untuk penyingkiran kedudukan sewenang-wenangnya yang kerap.

Langkah 5: Pendua, keadaan kosong, dan identiti nod.

Jujukan menyelesaikan kedua-dua susunan pendua dan pemutus seri popMax. Operasi kosong mengembalikan satu ralat yang konsisten. Setiap nod muncul tepat sekali dalam senarai dan sekali dalam indeks; alih keluar nod yang sama daripada kedua-dua struktur dan bukannya membina semula daripada nilainya sahaja.

Langkah 6: Uji susunan dan indeks.

Gunakan tatasusunan perlahan sebagai model rujukan. Uji [5,1,5] dengan dua panggilan popMax; ia sepatutnya menyingkirkan angka 5 bahagian atas dan kemudian angka 5 bahagian bawah. Sertakan nilai negatif, semua nilai sama, keadaan kosong, push/pop berselang-seli, nilai maksimum dalaman, penyingkiran berulang, dan jujukan rawak yang panjang. Selepas setiap operasi, sahkan susunan senarai, saiz indeks, dan peekMax.

Contoh jawapan berkualiti tinggi

“Saya akan menggunakan senarai berpaut ganda dua untuk susunan tindanan dan indeks tertib seimbang yang berkunci (value, sequence) untuk carian nilai maksimum. Jujukan adalah meningkat, jadi jujukan terbesar antara nilai maksimum yang sama adalah yang paling hampir dengan bahagian atas. Setiap nod membawa kedua-dua penunjuk senarai dan kunci indeksnya: pop mengambil ekor senarai, popMax mengambil ekor indeks, dan kedua-duanya menyingkirkan nod yang sama daripada struktur yang lain. Top ialah O(1), operasi selebihnya ialah O(log n), dan ruang ialah O(n). Jika penemuduga hanya memerlukan peekMax, saya akan menggunakan tindanan max bantuan untuk mengurangkan kerumitan pelaksanaan.”

Kesilapan lazim

• Hanya menyimpan satu nilai maksimum semasa → nilai maksimum seterusnya tidak diketahui selepas pemadaman → kekalkan indeks tertib yang boleh dicari.
• Menganggap popMax sebagai pop → kedudukan yang salah disingkirkan dan susunan tindanan berubah → cari nod mengikut indeks nilai, kemudian putuskan pautan melalui penunjuk senarai.
• Membiarkan pendua tanpa jujukan → nilai maksimum paling atas tidak dapat dibuktikan → gunakan (value, sequence) sebagai kunci.
• Menyingkirkan daripada indeks tetapi bukan daripada senarai → top boleh mengembalikan nod yang telah dipadamkan → kongsi identiti nod dan kemas kini kedua-dua struktur secara atomik.
• Mendakwa popMax adalah O(1) untuk reka bentuk tindanan bantuan → penyingkiran sewenang-wenangnya biasanya mengalihkan item atau membina semula keadaan → nyatakan batas terlunas dan kes terburuk dengan tepat.

Soalan susulan dan jawapan

Soalan susulan 1: Bolehkah setiap operasi menjadi O(1)?

Bagi integer lebar tetap, struktur berbaldi (bucketed) atau struktur keutamaan integer khusus adalah mungkin, tetapi batasannya bergantung pada lebar kunci, memori, dan model pengiraan. Bagi objek boleh banding sewenang-wenangnya, berikan penyelesaian indeks O(log n) yang jujur dan bukannya mencampurkan dakwaan terlunas, jangkaan, dan kes terburuk.

Soalan susulan 2: Bagaimanakah anda menjadikannya selamat untuk benang (thread-safe)?

Kontrak paling mudah melindungi setiap operasi majmuk dengan satu kunci (lock) supaya senarai dan indeks tertib tidak menyimpang buat sementara waktu. Keserentakan yang lebih tinggi mungkin menggunakan pemecahan (sharding) atau syot kilat tidak boleh ubah (immutable snapshots), tetapi popMax menyingkirkan daripada dua struktur secara atomik dan tidak boleh dibuat konsisten dengan hanya menganggap bahawa kunci yang diperoleh secara berasingan adalah mencukupi.

Soalan susulan 3: Bagaimana jika hanya peekMax, bukan popMax, yang diperlukan?

Gunakan tindanan utama dan tindanan max awalan dengan panjang yang sama. Push merekodkan nilai maksimum baharu dalam kedua-dua tindanan; pop menyingkirkan daripada kedua-duanya; top dan peekMax membaca bahagian atas masing-masing. Setiap operasi ialah O(1), dan nilai maksimum pendua mesti direkodkan berulang kali.