Petunjuk dan konteks
Implementasikan stack dengan push, pop, top, dan getMin. Setiap operasi harus berkinerja O(1), dan perilaku saat stack kosong harus dibuat eksplisit. Pertanyaan ini cocok untuk posisi coding, backend, dan library. Kuncinya adalah mempertahankan nilai minimum untuk setiap kedalaman stack, bukan menghafal sebuah API.
Apa yang sedang diuji oleh pewawancara
Invarian
Struktur tambahan pada kedalaman d menyimpan nilai minimum dari d nilai pertama. Stack utama dan stack tambahan selalu memiliki panjang yang sama.
Nilai minimum duplikat
Ketika sebuah nilai baru sama dengan nilai minimum saat ini, nilai tersebut tetap harus dicatat. Jika tidak, melakukan pop pada satu salinan akan menghilangkan nilai minimum yang benar.
Error dan batas (boundaries)
pop, top, dan getMin pada stack kosong memerlukan kontrak yang konsisten: exception, option, atau kode error. Sentinel tanpa peringatan (silent sentinel) tidaklah aman.
Kompleksitas
Setiap operasi hanya menyentuh bagian teratas (top), sehingga kompleksitas waktu adalah O(1) dan ruang tambahan adalah O(n). Melakukan pemindaian (scan) selama getMin tidak memenuhi persyaratan.
Pertanyaan untuk diklarifikasi terlebih dahulu
- Apa yang harus dikembalikan oleh operasi pada stack kosong: exception, option, atau kode error?
- Apakah nilai bisa bernilai negatif, berulang, atau mendekati batas integer?
- Apakah diperlukan comparator generik, atau hanya untuk integer?
- Apakah API harus mengembalikan indeks minimum atau jumlah kemunculan?
- Apakah diperlukan thread safety atau implementasi lock-free?
- Apakah pengujian harus mencakup pemanggilan individual atau urutan operasi acak?
Jawaban 30 detik
“Saya akan mempertahankan dua stack dengan panjang yang sama: values dan mins. Bagian atas dari mins menyimpan nilai minimum dari semua nilai yang ada saat ini. Pada push, saya melakukan push min(x, minimum saat ini); pada pop, saya melakukan pop pada keduanya; top dan getMin membaca elemen teratas yang relevan. Setiap operasi adalah O(1), dengan ruang tambahan O(n). Saya mencatat nilai minimum duplikat, menentukan kontrak error stack kosong, dan memverifikasi urutan acak terhadap daftar referensi yang lebih lambat.”
Jawaban mendalam langkah demi langkah
Langkah 1: Nyatakan invarian
Misalkan S adalah stack nilai dan M adalah stack tambahan. Untuk setiap kedalaman d, M[d] sama dengan nilai minimum dari S[0..d]. Panjang keduanya selalu sama.
Langkah 2: Rancang push
Jika M tidak kosong, lakukan push min(x, M.top()) ke M; jika tidak, lakukan push x. Kemudian lakukan push x ke S. Elemen teratas tambahan yang baru adalah prefix minimum.
Langkah 3: Rancang pop dan kueri
Pop menghapus satu item dari kedua stack. top membaca S.top(), dan getMin membaca M.top(). Tidak diperlukan pemindaian.
Langkah 4: Pertahankan duplikat
Setelah melakukan push 2, 1, 1, M bernilai 2, 1, 1. Melakukan pop satu kali harus tetap mengembalikan 1. Hanya mencatat nilai yang lebih kecil secara ketat akan merusak invarian.
Langkah 5: Tentukan error dan tipe
Stack kosong dapat melempar EmptyStackError atau mengembalikan Result bertipe. Implementasi generik harus menerima comparator total-order dan mendefinisikan kesetaraan secara konsisten.
Langkah 6: Buktikan dan uji kompleksitas
Keempat operasi adalah O(1), dengan ruang tambahan O(n). Pengujian acak dapat mempertahankan list biasa sebagai oracle dan membandingkan top, minimum, ukuran, dan error setelah setiap operasi.
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
Contoh jawaban model
“Saya akan mempertahankan values dan mins. mins[i] adalah nilai minimum dari values[0..i], sehingga kedua stack memiliki panjang yang sama. push menyimpan nilai beserta prefix minimum barunya; stack mins yang kosong akan menyimpan nilai tersebut secara langsung. pop menghapus dari keduanya, sedangkan top dan getMin membaca elemen teratas yang sesuai.
Nilai minimum duplikat harus disimpan. Untuk 2, 1, 1, mins adalah 2, 1, 1; jika tidak, satu kali pop akan secara keliru mengembalikan 2. Operasi kosong menggunakan kontrak error yang eksplisit. Kompleksitas waktu adalah O(1) per operasi dan ruang tambahan adalah O(n). Saya akan menguji urutan kosong, negatif, duplikat, bergantian, dan acak terhadap oracle berbasis list.”
Kesalahan umum
- Memindai stack nilai selama getMin, menjadikannya O(n).
- Hanya mencatat nilai yang lebih kecil secara ketat sehingga kehilangan nilai minimum duplikat.
- Hanya melakukan pop pada stack utama dan membuat kedua struktur tidak sinkron.
- Menyimpan satu nilai minimum global yang tidak dapat dipulihkan setelah pop.
- Mengembalikan nol untuk stack kosong sehingga membingungkannya dengan input yang valid.
- Mengabaikan nilai negatif atau batas integer.
- Menyebut batas teramortisasi sebagai O(1) ketat tanpa justifikasi.
- Mengklaim dukungan objek generik tanpa mendefinisikan comparator.
Pertanyaan lanjutan
Lanjutan 1: Bisakah Anda menggunakan satu stack?
Ya. Simpan pasangan nilai dan prefix minimum di setiap entri. Invarian tidak berubah dan ruang tetap O(n).
Lanjutan 2: Bagaimana Anda menambahkan getMax?
Pertahankan juga stack maximum-prefix, atau simpan nilai, min, dan max di setiap entri. Waktu tetap O(1) per operasi dan total ruang O(n).
Lanjutan 3: Bagaimana Anda mengembalikan jumlah minimum?
Simpan min dan count di setiap entri tambahan. Nilai yang sama akan menambah count, dan pop memulihkan entri sebelumnya. Tentukan semantik duplikat dan rollback secara eksplisit.
Lanjutan 4: Bagaimana Anda membuatnya aman untuk thread (thread-safe)?
Lindungi kedua stack dengan satu mutex di sekitar setiap operasi logis. Penguncian terpisah dapat mengekspos status perantara yang tidak konsisten. Desain lock-free memerlukan atomic composite state dan pembahasan reklamasi memori.
Lanjutan 5: Bagaimana Anda membuktikan kebenarannya?
Gunakan induksi. Stack kosong memenuhi invarian; push menghitung prefix minimum baru; pop memulihkan rekaman sebelumnya. Oleh karena itu, getMin selalu mengembalikan nilai minimum dari stack nilai saat ini.