Wawancara Koding: Bagaimana Cara Mendesain Max Stack dengan popMax?

Masalah dan konteks

Implementasikan MaxStack: push(x) menambahkan item, pop() menghapus dan mengembalikan elemen teratas, top() membaca elemen teratas, peekMax() membaca nilai maksimum, dan popMax() menghapus dan mengembalikan nilai maksimum yang paling dekat dengan posisi teratas. Nilai maksimum yang berulang menggunakan aturan penentu last-in-first-out; perilaku stack kosong harus berupa error eksplisit atau hasil kosong.

Masalah LeetCode publik dan catatan pertanyaan wawancara baru-baru ini menggunakan antarmuka ini. Ini berbeda dari stack prefix-minimum: popMax harus menemukan node interior dan memulihkan urutan stack yang tersisa.

Apa yang sedang diuji oleh pewawancara

• Apakah Anda menentukan aturan penentu untuk nilai maksimum duplikat dan kontrak stack kosong terlebih dahulu.
• Apakah Anda dapat menjelaskan mengapa satu variabel currentMax tidak dapat memulihkan nilai maksimum berikutnya setelah penghapusan.
• Apakah Anda memisahkan urutan stack dari urutan nilai dan menghapus node yang sama dari kedua indeks.
• Apakah Anda membedakan desain stack pembantu dengan waktu teramortisasi O(1) dari desain indeks terurut O(log n).

Klarifikasi sebelum menulis kode

1. Apakah popMax harus berupa O(1), teramortisasi O(1), atau boleh berupa O(log n)? Hal ini menentukan struktur data.
2. Untuk nilai maksimum duplikat, apakah item yang paling dekat dengan posisi teratas harus dihapus, atau nilai maksimum mana pun dapat diterima? Aturan ini mengubah pencarian indeks.
3. Apakah diperlukan iterator yang stabil, panggilan konkuren, atau persistensi? Hal-hal tersebut mengubah masa hidup node dan penguncian (locking).
4. Apakah nilainya berupa objek yang dapat dibandingkan atau integer terbatas? Integer terbatas memungkinkan penggunaan bucket; objek generik biasanya memerlukan indeks perbandingan.

Jawaban 30 detik

“Saya membungkus setiap nilai dalam sebuah node dengan nomor urut yang meningkat secara monoton. Doubly linked list mempertahankan urutan stack; indeks terurut mengurutkan berdasarkan (value, sequence), sehingga entri terakhirnya adalah nilai maksimum yang paling dekat dengan bagian atas. top membaca ekor list, peekMax membaca ekor indeks, dan popMax mengambil node tersebut lalu melepaskan tautannya melalui pointer list-nya. Dengan indeks balanced-tree, push, pop, peekMax, dan popMax berukuran O(log n), sedangkan top berukuran O(1). Jika hanya operasi top dan peekMax yang memerlukan waktu konstan, max stack pembantu lebih sederhana, tetapi popMax tidak bisa secara jujur tetap O(1).”

Penjelasan mendalam langkah demi langkah

Langkah 1: Pisahkan urutan stack dari urutan terurut.

Setiap node menyimpan value, sebuah sequence yang meningkat secara monoton, prev, dan next. Ekor list adalah bagian atas stack. Kunci terurut adalah (value, sequence); untuk nilai yang sama, urutan yang lebih besar diurutkan lebih belakang, menjadikan ekor indeks sebagai nilai maksimum yang paling dekat dengan posisi teratas.

Langkah 2: Pilih indeks terurut yang dapat dihapus.

Gunakan balanced tree yang mendukung duplikat, TreeMap ditambah set node terurut, atau indeks dua tingkat dari nilai ke ID urutan terurut. Satu variabel currentMax saja tidak cukup: setelah menghapusnya, nilai maksimum berikutnya beserta nodenya harus ditemukan.

Langkah 3: Jaga kelima operasi tetap tersinkronisasi.

• push: buat node, tambahkan ke list, dan masukkan ke dalam indeks terurut.
• pop: ambil ekor list, hapus node tersebut dari indeks terurut, lalu lepaskan tautannya.
• top: kembalikan nilai ekor list.
• peekMax: kembalikan nilai ekor indeks terurut.
• popMax: ambil ekor indeks terurut, lepaskan tautannya melalui pointer list-nya, lalu hapus dari indeks.

Pseudocode menunjukkan invarian utama; API tree konkret bersifat spesifik untuk setiap bahasa:

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

Langkah 4: Kompleksitas dan alternatif yang lebih sederhana.

Dengan balanced tree, top adalah O(1) dan operasi indeks lainnya adalah O(log n); ruang yang dibutuhkan adalah O(n). Jika popMax teramortisasi O(n) dapat diterima, sebuah main stack ditambah prefix-max stack mencatat nilai maksimum di setiap kedalaman. Hal itu lebih mudah, tetapi tidak cocok untuk penghapusan posisi sembarang yang sering dilakukan.

Langkah 5: Duplikat, status kosong, dan identitas node.

Urutan menyelesaikan pengurutan duplikat sekaligus penentu popMax. Operasi kosong mengembalikan satu error yang konsisten. Setiap node muncul tepat satu kali di list dan satu kali di indeks; hapus node yang sama dari kedua struktur daripada merekonstruksinya hanya dari nilainya.

Langkah 6: Uji urutan dan indeks.

Gunakan array lambat sebagai model referensi. Uji [5,1,5] dengan dua panggilan popMax; ini harus menghapus angka 5 di atas kemudian angka 5 di bawah. Uji nilai negatif, nilai yang semuanya sama, status kosong, push/pop bergantian, nilai maksimum interior, penghapusan berulang, dan urutan acak yang panjang. Setelah setiap operasi, verifikasi urutan list, ukuran indeks, dan peekMax.

Contoh jawaban berkualitas tinggi

“Saya akan menggunakan doubly linked list untuk urutan stack dan indeks terurut seimbang yang dikunci oleh (value, sequence) untuk pencarian nilai maksimum. Nomor urutnya meningkat, sehingga urutan terbesar di antara nilai maksimum yang sama adalah yang paling dekat dengan bagian atas. Setiap node membawa pointer list dan kunci indeksnya: pop mengambil ekor list, popMax mengambil ekor indeks, dan keduanya menghapus node yang sama dari struktur lainnya. Top adalah O(1), operasi yang tersisa adalah O(log n), dan ruang yang dibutuhkan adalah O(n). Jika pewawancara hanya membutuhkan peekMax, saya akan menggunakan max stack pembantu untuk mengurangi kompleksitas implementasi.”

Kesalahan umum

• Hanya menyimpan satu nilai maksimum saat ini → nilai maksimum berikutnya tidak diketahui setelah penghapusan → pertahankan indeks terurut yang dapat dicari.
• Memperlakukan popMax seperti pop → posisi yang salah dihapus dan urutan stack berubah → temukan node berdasarkan indeks nilai, lalu lepaskan tautan berdasarkan pointer list.
• Membiarkan duplikat tanpa nomor urut → nilai maksimum teratas tidak dapat dibuktikan → gunakan (value, sequence) sebagai kunci.
• Menghapus dari indeks tetapi tidak dari list → top dapat mengembalikan node yang telah dihapus → bagikan identitas node dan perbarui kedua struktur secara atomik.
• Mengklaim popMax adalah O(1) untuk desain stack pembantu → penghapusan sembarang biasanya memindahkan item atau membangun ulang status → sebutkan batas teramortisasi dan kasus terburuk secara tepat.

Pertanyaan lanjutan dan jawaban

Pertanyaan lanjutan 1: Bisakah setiap operasi menjadi O(1)?

Untuk integer dengan lebar tetap, struktur bucketed atau struktur prioritas integer khusus dimungkinkan, tetapi batasannya bergantung pada lebar kunci, memori, dan model komputasi. Untuk objek acak yang dapat dibandingkan, berikan solusi indeks O(log n) yang jujur alih-alih mencampuradukkan klaim teramortisasi, ekspektasi, dan kasus terburuk.

Pertanyaan lanjutan 2: Bagaimana Anda membuatnya thread-safe?

Kontrak paling sederhana melindungi setiap operasi gabungan dengan satu kunci (lock) sehingga list dan indeks terurut tidak berbeda untuk sementara waktu. Konkurensi yang lebih tinggi dapat menggunakan sharding atau snapshot yang tidak dapat diubah (immutable), tetapi popMax menghapus dari dua struktur secara atomik dan tidak dapat dibuat konsisten hanya dengan berasumsi bahwa kunci yang diperoleh secara terpisah sudah cukup.

Pertanyaan lanjutan 3: Bagaimana jika hanya peekMax, bukan popMax, yang diperlukan?

Gunakan main stack dan prefix-max stack dengan panjang yang sama. Push mencatat nilai maksimum baru di kedua stack; pop menghapus dari keduanya; top dan peekMax membaca elemen teratasnya masing-masing. Setiap operasi adalah O(1), dan nilai maksimum duplikat harus dicatat berulang kali.