Gesaan dan konteks
Anda mewarisi MedianFinder dengan timbunan maksimum (max-heap) untuk bahagian bawah dan timbunan minimum (min-heap) untuk bahagian atas. Ia berfungsi untuk 1, 2, 3, namun gagal pada jujukan seperti 10, 1, 9, 2, input yang banyak mengandungi pendua dan integer ekstrem. Tugas anda adalah untuk menyahpepijat pelaksanaan sedia ada, bukan membina struktur data standard dari awal.
Perkara yang dinilai oleh penemu duga
- Sama ada anda menyatakan invariant sebelum mengubah kod.
- Sama ada anda boleh mengecilkan jujukan yang gagal dan mengenal pasti keadaan tidak sah yang pertama.
- Sama ada pembaikan mengendalikan pertanyaan kosong, pendua dan limpahan panjang genap.
- Sama ada bukti dan kekompleksan sepadan dengan kod.
Soalan penjelasan untuk ditanya
- Apakah yang patut dilakukan oleh
findMedian()sebelum pemasukan pertama? - Timbunan manakah yang boleh mengandungi elemen tambahan?
- Apakah lebar integer yang diterima oleh API, dan apakah jenis yang dikembalikan oleh median?
- Bolehkah pendua muncul, dan adakah akses serentak (concurrency) dalam skop?
Andaikan pendua adalah sah, timbunan bawah boleh mempunyai satu elemen tambahan, pertanyaan mengembalikan nilai titik apung (floating-point), dan carian semasa kosong mencetuskan ralat yang didokumenkan. Keserempakan adalah di luar skop tugasan pengekodan ini.
Jawapan 30 saat
"Saya akan mengukur kedua-dua timbunan selepas setiap pemasukan dan menegaskan dua invariant: saiz kedua-duanya berbeza paling banyak satu dengan timbunan bawah lebih besar, dan setiap nilai bawah tidak lebih besar daripada setiap nilai atas, yang boleh disemak pada bahagian atas (tops) timbunan. Saya akan meminimumkan input pertama yang gagal, kemudian membaiki pemasukan dengan menolak ke dalam timbunan bawah, memindahkan nilai maksimumnya ke timbunan atas, dan memindahkan semula nilai minimum atas hanya apabila ia lebih besar. Carian median menggunakan bahagian atas bawah untuk saiz ganjil dan purata selamat-limpahan bagi kedua-dua bahagian atas untuk saiz genap. Akhir sekali, saya akan menjalankan oracle tatasusunan diisih ke atas jujukan pendek yang menyeluruh dan ekstrem bertentangan."
Analisis terperinci langkah demi langkah
1. Jadikan kegagalan boleh diperhatikan
Selepas setiap pemasukan, rekodkan awalan input, kedua-dua saiz timbunan dan kedua-dua bahagian atas. Berhenti pada invariant pertama yang dilanggar. Lakukan delta-debug pada jujukan dengan membuang nilai selagi kegagalan berterusan. Contoh lawan empat nilai lebih berguna daripada seribu nilai rawak.
2. Baiki dengan satu laluan pemasukan deterministik
Gunakan timbunan bawah sebagai titik masuk. Tolak x, pindahkan nilai maksimumnya ke timbunan atas, kemudian pindahkan semula nilai minimum atas jika timbunan atas menjadi lebih besar. Jujukan ini memulihkan susunan sebelum saiz. Dengan pustaka bahasa yang hanya menyediakan min-heap, simpan nilai yang dinegatifkan dalam timbunan bawah dan kekalkan penukaran tanda pada sempadan.
3. Jadikan carian selamat
Tolak carian apabila kedua-dua timbunan kosong. Untuk bilangan ganjil, kembalikan nilai maksimum bawah. Untuk bilangan genap, tukarkan kedua-dua titik hujung kepada jenis yang lebih luas atau jenis titik apung sebelum menambah; (a + b) / 2 boleh melimpah dalam jenis integer lebar tetap walaupun median boleh diwakili.
4. Buktikan dan uji pembaikan
Memindahkan nilai maksimum bawah ke bahagian atas menjamin nilai bawah yang tinggal tidak melebihi sempadan yang dipindahkan. Memindahkan semula satu nilai minimum atas memulihkan peraturan saiz yang dipilih tanpa merosakkan susunan. Setiap pemasukan melaksanakan bilangan operasi timbunan yang tetap, jadi ia adalah O(log n); carian membaca satu atau dua bahagian atas dalam O(1), dan storan adalah O(n).
Gunakan oracle senarai diisih selepas setiap awalan. Liputi carian kosong, satu nilai, dua nilai ekstrem, menaik, menurun, berselang-seli rendah/tinggi, semua pendua, nilai negatif dan banyak peralihan antara saiz ganjil dan genap.
Contoh jawapan yang kukuh
"Saya tidak akan menampal cabang yang kebetulan gagal. Saya akan menegaskan lower.size == upper.size atau lower.size == upper.size + 1 terlebih dahulu, serta max(lower) <= min(upper) setiap kali kedua-duanya wujud. Pada setiap add, saya menolak ke dalam bahagian bawah, memindahkan nilai maksimumnya ke bahagian atas, kemudian memindahkan semula nilai minimum atas hanya jika bahagian atas lebih besar. Ini menjadikan pemulihan susunan tidak bergantung pada corak input sebelumnya.
findMedian menolak struktur yang kosong. Strim bersaiz ganjil mengembalikan bahagian atas bawah; strim bersaiz genap menukar kedua-dua bahagian atas sebelum mengambil purata supaya integer ekstrem tidak melimpah. Saya akan membandingkan setiap awalan dengan oracle tatasusunan diisih untuk jujukan pendek yang menyeluruh daripada nilai negatif, sifar, pendua dan nilai ekstrem. Pelaksanaan teras kekal O(log n) bagi setiap penambahan, O(1) bagi setiap pertanyaan, dan ruang O(n)."
Kesilapan lazim
- Hanya mengimbangi saiz → timbunan mungkin mengandungi nilai yang bersilang (crossed values) → tegaskan susunan bahagian atas sebagai invariant yang berasingan.
- Memilih cabang daripada nilai masuk sahaja → keadaan timbunan sebelumnya mungkin masih tidak sah → gunakan jujukan pemindahan antara timbunan yang deterministik.
- Mengambil purata dalam jenis integer input → titik hujung ekstrem boleh melimpah → luaskan jenis data sebelum penambahan.
- Menguji nilai unik yang diisih sahaja → pendua dan ekstrem berselang-seli menyembunyikan ralat percabangan → gunakan oracle awalan dan jujukan bertentangan.
- Mendakwa pemasukan
O(1)→ operasi tolak dan pop timbunan adalah logaritma → kira operasi timbunan yang sebenar.
Soalan susulan dan respons
Bagaimanakah anda mencari input gagal yang paling kecil?
Teruskan memadam satu elemen atau satu ketulan bersebelahan dan jalankan semula semakan invariant. Kekalkan awalan terpendek yang pemasukan terakhirnya mula-mula melanggar susunan atau saiz, kemudian periksa peralihan itu sahaja.
Mengapakah pendua tidak memerlukan pengendalian khas?
Invariant menggunakan <=, jadi nilai yang sama boleh berada di mana-mana bahagian. Saiz timbunan menentukan salinan sama yang mana menyumbang kepada median; identiti elemen tidak penting.
Bagaimanakah anda menguji tanpa mempercayai pelaksanaan timbunan lain?
Untuk input kecil, salin awalan, isihkannya, dan kira median matematik secara terus. Uji semua jujukan pada abjad yang kecil, kemudian tambahkan nilai ekstrem lebar tetap dan kes rawak yang lebih besar.
Adakah ini menyokong tetingkap gelongsor (sliding window)?
Tidak. Mengeluarkan nilai luput arbitrari memerlukan pemadaman berindeks atau pembilang pemadaman malas (lazy-deletion counters) dalam kedua-dua timbunan. Itu adalah tugas yang berbeza dan tidak sepatutnya disembunyikan di dalam pembaikan ini.