Perintah dan konteks
Anda mewarisi sebuah MedianFinder dengan max-heap untuk bagian bawah dan min-heap untuk bagian atas. Ini bekerja untuk 1, 2, 3, namun gagal pada urutan seperti 10, 1, 9, 2, input yang sarat duplikat, dan bilangan bulat ekstrem. Tugasnya adalah men-debug implementasi yang ada, bukan membuat struktur data standar dari awal.
Apa yang dievaluasi pewawancara
- Apakah Anda menyatakan invarian sebelum mengubah kode.
- Apakah Anda dapat memperkecil urutan yang gagal dan mengidentifikasi status tidak valid pertama.
- Apakah perbaikan tersebut menangani kueri kosong, duplikat, dan overflow pada panjang genap.
- Apakah pembuktian dan kompleksitas sesuai dengan kode.
Pertanyaan klarifikasi yang perlu diajukan
- Apa yang harus dilakukan
findMedian()sebelum penyisipan pertama? - Heap mana yang boleh berisi elemen tambahan?
- Berapa lebar integer yang diterima API, dan tipe apa yang dikembalikan oleh median?
- Apakah duplikat boleh muncul, dan apakah akses bersamaan (concurrency) termasuk dalam cakupan?
Asumsikan duplikat valid, heap bawah boleh memiliki satu elemen tambahan, kueri mengembalikan nilai floating-point, dan pencarian saat kosong memunculkan error yang terdokumentasi. Konkurensi berada di luar tugas coding ini.
Jawaban 30 detik
"Saya akan menginstrumentasikan kedua heap setelah setiap penyisipan dan menegaskan dua invarian: ukuran keduanya berbeda paling banyak satu dengan heap bawah lebih besar, dan setiap nilai bawah tidak lebih besar dari setiap nilai atas, yang dapat diperiksa di puncak heap. Saya akan meminimalkan input pertama yang gagal, lalu memperbaiki penyisipan dengan memasukkan ke heap bawah, memindahkan nilai maksimumnya ke heap atas, dan memindahkan kembali nilai minimum atas hanya jika heap atas menjadi lebih besar. Pencarian median menggunakan puncak bawah untuk ukuran ganjil dan rata-rata yang aman dari overflow dari kedua puncak untuk ukuran genap. Terakhir, saya akan menjalankan oracle array terurut pada urutan pendek yang komprehensif dan nilai ekstrem adversarial."
Pembahasan mendalam langkah demi langkah
1. Buat kegagalan dapat diamati
Setelah setiap penyisipan, catat awalan input, kedua ukuran heap, dan kedua puncak heap. Berhenti pada invarian pertama yang rusak. Lakukan delta-debugging pada urutan dengan menghapus nilai selama kegagalan masih terjadi. Contoh lawan (counterexample) empat nilai lebih berguna daripada seribu nilai acak.
2. Perbaiki dengan satu jalur penyisipan deterministik
Gunakan heap bawah sebagai titik masuk. Masukkan x, pindahkan nilai maksimumnya ke heap atas, lalu pindahkan kembali nilai minimum atas jika heap atas menjadi lebih besar. Urutan ini memulihkan pengurutan sebelum ukuran. Dengan pustaka bahasa yang hanya menyediakan min-heap, simpan nilai negatif di heap bawah dan pertahankan konversi tanda di batas pemisah.
3. Buat pencarian menjadi aman
Tolak pencarian ketika kedua heap kosong. Untuk jumlah ganjil, kembalikan nilai maksimum bawah. Untuk jumlah genap, konversikan kedua titik ujung ke tipe yang lebih lebar atau tipe floating-point sebelum menjumlahkan; (a + b) / 2 dapat mengalami overflow pada tipe integer lebar-tetap bahkan ketika median dapat direpresentasikan.
4. Buktikan dan uji perbaikan
Memindahkan nilai maksimum bawah ke sisi atas menjamin nilai bawah yang tersisa tidak melebihi batas yang dipindahkan. Memindahkan kembali satu nilai minimum atas memulihkan aturan ukuran yang dipilih tanpa merusak pengurutan. Setiap penyisipan melakukan sejumlah operasi heap yang konstan, sehingga berbobot O(log n); pencarian membaca satu atau dua puncak dalam O(1), dan ruang penyimpanan adalah O(n).
Gunakan oracle daftar terurut setelah setiap awalan. Cakup pencarian kosong, satu nilai, dua nilai ekstrem, urutan naik, urutan turun, bergantian rendah/tinggi, semua duplikat, nilai negatif, dan banyak transisi antara ukuran ganjil dan genap.
Contoh jawaban yang kuat
"Saya tidak akan menambal percabangan yang kebetulan gagal. Saya pertama-tama akan menegaskan lower.size == upper.size atau lower.size == upper.size + 1, ditambah max(lower) <= min(upper) kapan pun keduanya ada. Pada setiap add, saya memasukkan ke heap bawah, memindahkan nilai maksimumnya ke atas, lalu memindahkan kembali nilai minimum atas hanya jika bagian atas lebih besar. Hal itu membuat pemulihan pengurutan menjadi independen dari pola input sebelumnya.
findMedian menolak struktur yang kosong. Stream berukuran ganjil mengembalikan puncak bawah; stream berukuran genap mengonversi kedua puncak sebelum merata-ratakan agar integer ekstrem tidak mengalami overflow. Saya akan membandingkan setiap awalan terhadap oracle array terurut untuk urutan pendek komprehensif yang diambil dari nilai negatif, nol, duplikat, dan nilai ekstrem. Implementasi inti tetap berupa O(log n) per penambahan, O(1) per kueri, dan ruang O(n)."
Kesalahan umum
- Hanya menyeimbangkan ukuran → heap dapat berisi nilai yang saling tumpang-tindih (crossed) → tegaskan pengurutan puncak sebagai invarian terpisah.
- Memilih cabang hanya dari nilai yang masuk → status heap sebelumnya masih bisa tidak valid → gunakan urutan perpindahan antar-heap yang deterministik.
- Merata-ratakan dalam tipe integer input → titik ujung ekstrem dapat meluap (overflow) → perlebar tipe sebelum penjumlahan.
- Hanya menguji nilai unik yang terurut → duplikat dan ekstrem yang bergantian menyembunyikan error percabangan → gunakan oracle awalan dan urutan adversarial.
- Mengklaim penyisipan
O(1)→ push dan pop pada heap bersifat logaritmik → hitung operasi heap yang sebenarnya.
Pertanyaan lanjutan dan respons
Bagaimana Anda menemukan input gagal terkecil?
Terus hapus satu elemen atau satu potongan berdekatan dan jalankan kembali pemeriksaan invarian. Pertahankan awalan terpendek yang penyisipan terakhirnya pertama kali melanggar urutan atau ukuran, lalu periksa hanya transisi tersebut.
Mengapa nilai duplikat tidak memerlukan penanganan khusus?
Invarian menggunakan <=, sehingga nilai yang sama dapat berada di kedua sisi. Ukuran heap menentukan salinan sama mana yang berkontribusi pada median; identitas elemen tidak menjadi masalah.
Bagaimana Anda menguji tanpa memercayai implementasi heap lainnya?
Untuk input kecil, salin awalan, urutkan, dan hitung median matematika secara langsung. Uji semua kemungkinan urutan pada alfabet kecil, lalu tambahkan nilai ekstrem fixed-width dan kasus acak yang lebih besar.
Apakah ini mendukung sliding window?
Tidak. Menghapus nilai kedaluwarsa arbitrer memerlukan penghapusan terindeks atau penghitung lazy-deletion di kedua heap. Itu adalah tugas yang berbeda dan tidak boleh disembunyikan di dalam perbaikan ini.