Gesaan dan konteks
Laksanakan tindanan dengan push, pop, top, dan getMin. Setiap operasi mestilah O(1), dan tingkah laku tindanan kosong mestilah jelas. Soalan ini sesuai untuk peranan pengekodan, bahagian belakang (backend), dan perpustakaan. Kuncinya adalah mengekalkan nilai minimum untuk setiap kedalaman tindanan, bukan menghafal sesuatu API.
Perkara yang diuji oleh penemu duga
Varian tak berubah (invariant)
Struktur bantuan pada kedalaman d menyimpan nilai minimum bagi d nilai pertama. Tindanan utama dan bantuan kekal sama panjang.
Minimum pendua
Apabila nilai baharu sama dengan minimum semasa, ia masih mesti direkodkan. Jika tidak, melakukan pop pada satu salinan akan kehilangan minimum yang betul.
Ralat dan sempadan
pop, top, dan getMin pada tindanan kosong memerlukan kontrak yang konsisten: pengecualian (exception), pilihan (option), atau kod ralat. Nilai sentinel senyap adalah tidak selamat.
Kekompleksan
Setiap operasi hanya menyentuh bahagian atas, jadi masa adalah O(1) dan ruang tambahan adalah O(n). Imbasan semasa getMin tidak memenuhi keperluan.
Soalan untuk dijelaskan terlebih dahulu
- Apakah yang patut dikembalikan oleh operasi kosong: pengecualian, pilihan, atau kod ralat?
- Bolehkah nilai menjadi negatif, berulang, atau mendekati had integer?
- Adakah pembanding generik diperlukan, atau hanya integer?
- Patutkah API mengembalikan indeks minimum atau kiraan kemunculan?
- Adakah keselamatan bebenang (thread safety) atau pelaksanaan tanpa kunci (lock-free) diperlukan?
- Patutkah ujian merangkumi panggilan individu atau jujukan operasi rawak?
Jawapan 30 saat
“Saya akan mengekalkan dua tindanan yang sama panjang: values dan mins. Bahagian atas mins menyimpan nilai minimum bagi semua nilai yang ada pada masa ini. Semasa push, saya menolak min(x, minimum semasa); semasa pop, saya mengeluarkan kedua-duanya; top dan getMin membaca bahagian atas yang berkaitan. Setiap operasi adalah O(1), dengan O(n) ruang tambahan. Saya merekodkan minimum pendua, mentakrifkan kontrak ralat tindanan kosong, dan menyemak jujukan rawak terhadap senarai rujukan yang lebih perlahan.”
Jawapan mendalam langkah demi langkah
Langkah 1: Nyatakan varian tak berubah
Biarkan S menjadi tindanan nilai dan M menjadi tindanan bantuan. Untuk setiap kedalaman d, M[d] bersamaan dengan minimum S[0..d]. Panjang kedua-duanya sentiasa sama.
Langkah 2: Reka bentuk push
Jika M tidak kosong, tolak min(x, M.top()) ke atas M; jika tidak tolak x. Kemudian tolak x ke atas S. Bahagian atas bantuan yang baharu ialah prefix minimum.
Langkah 3: Reka bentuk pop dan pertanyaan
Pop membuang satu item daripada kedua-dua tindanan. top membaca S.top(), dan getMin membaca M.top(). Tiada imbasan diperlukan.
Langkah 4: Kekalkan pendua
Selepas menolak 2, 1, 1, M ialah 2, 1, 1. Mengeluarkan (pop) sekali masih mesti mengembalikan 1. Merekodkan hanya nilai yang lebih kecil secara ketat akan merosakkan varian tak berubah.
Langkah 5: Takrifkan ralat dan jenis
Tindanan kosong boleh melontarkan EmptyStackError atau mengembalikan Result ditaip. Pelaksanaan generik harus menerima pembanding tertib penuh dan mentakrifkan kesaksamaan secara konsisten.
Langkah 6: Buktikan dan uji kekompleksan
Kesemua empat operasi adalah O(1), dengan O(n) ruang bantuan. Ujian rawak boleh mengekalkan senarai biasa sebagai orakel dan membandingkan top, minimum, saiz, dan ralat selepas setiap operasi.
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
Jawapan model
“Saya akan mengekalkan values dan mins. mins[i] ialah minimum bagi values[0..i], jadi tindanan mempunyai panjang yang sama. push menyimpan nilai dan prefix minimum baharunya; tindanan mins yang kosong menyimpan nilai tersebut secara terus. pop mengeluarkan daripada kedua-duanya, manakala top dan getMin membaca bahagian atas yang sepadan.
Minimum pendua mesti disimpan. Untuk 2, 1, 1, mins ialah 2, 1, 1; jika tidak, satu pop akan tersilap mengembalikan 2. Operasi kosong menggunakan kontrak ralat yang jelas. Masa adalah O(1) bagi setiap operasi dan ruang tambahan adalah O(n). Saya akan menguji jujukan kosong, negatif, pendua, berselang-seli, dan rawak terhadap orakel berasaskan senarai.”
Kesilapan biasa
- Mengimbas tindanan nilai semasa getMin, menjadikannya O(n).
- Merekodkan hanya nilai yang lebih kecil secara ketat dan kehilangan minimum pendua.
- Mengeluarkan hanya tindanan utama dan menyahsegerakkan struktur.
- Menyimpan satu minimum global yang tidak boleh dipulihkan selepas pop.
- Mengembalikan sifar untuk tindanan kosong dan mengelirukannya dengan input yang sah.
- Mengabaikan nilai negatif atau had integer.
- Memanggil batas terpelunas (amortized bound) sebagai O(1) ketat tanpa justifikasi.
- Mendakwa sokongan objek generik tanpa mentakrifkan pembanding.
Soalan susulan
Susulan 1: Bolehkah anda menggunakan satu tindanan?
Ya. Simpan pasangan nilai dan prefix minimum dalam setiap entri. Varian tak berubah tidak berubah dan ruang kekal O(n).
Susulan 2: Bagaimanakah anda menambah getMax?
Kekalkan tindanan maximum-prefix juga, atau simpan value, min, dan max dalam setiap entri. Masa kekal O(1) bagi setiap operasi dan jumlah ruang O(n).
Susulan 3: Bagaimanakah anda mengembalikan kiraan minimum?
Simpan min dan count dalam setiap entri bantuan. Nilai yang sama menambah count, dan pop memulihkan entri sebelumnya. Takrifkan semantik pendua dan pengembalian semula (rollback) secara eksplisit.
Susulan 4: Bagaimanakah anda menjadikannya selamat untuk bebenang (thread-safe)?
Lindungi kedua-dua tindanan dengan satu mutex di sekitar setiap operasi logik. Kunci yang berasingan boleh mendedahkan keadaan perantaraan yang tidak konsisten. Reka bentuk tanpa kunci memerlukan keadaan komposit atomik dan perbincangan penebusan semula memori.
Susulan 5: Bagaimanakah anda membuktikan ketepatan?
Gunakan aruhan (induction). Tindanan kosong memenuhi varian tak berubah; push mengira prefix minimum baharu; pop memulihkan rekod sebelumnya. Oleh itu getMin sentiasa mengembalikan minimum tindanan nilai semasa.