Temuduga Pengekodan: Cari Median daripada Aliran Data

Masalah dan Konteks yang Berkenaan

Reka bentuk MedianFinder dengan dua operasi:

• addNum(num) menambah integer ke dalam aliran.
• findMedian() mengembalikan median setiap nilai yang dilihat setakat ini. Dengan bilangan ganjil, ia mengembalikan nilai tengah; dengan bilangan genap, ia mengembalikan purata dua nilai tengah.

Anggap hanya kemasukan sahaja, tanpa pemadaman, dan bahawa findMedian() dipanggil hanya selepas sekurang-kurangnya satu kemasukan. Input mungkin termasuk nombor negatif, pendua, dan integer bertanda 32-bit, dengan paling banyak 50,000 operasi. Sasarannya ialah O(log n) bagi setiap kemasukan, O(1) bagi setiap pertanyaan, dan ruang O(n).

Sebagai contoh, selepas memasukkan 5, 2, 10, 4, median berjalan ialah 5, 3.5, 5, 4.5. Mengisih pada setiap pertanyaan adalah betul tetapi memerlukan kos O(n log n) bagi setiap pertanyaan. Mengekalkan tatasusunan yang tersusun sepenuhnya menjadikan pertanyaan O(1), tetapi memasukkan di tengah masih menganjak O(n) elemen.

Bahan persediaan temuduga awam pada tahun 2026 terus membentangkan ini sebagai masalah pengekodan dua-heap yang representatif. Ia terpakai kepada pusingan pengekodan perisian umum, bahagian belakang, data, dan infrastruktur. Isyarat yang berguna bukan mengingat semula frasa "max-heap ditambah min-heap." Ia adalah menerbitkan struktur daripada pertanyaan, menyatakan kedua-dua invarian, dan membuktikan mengapa urutan pemindahan tetap mengekalkan partition.

Apa yang Dinilai oleh Penemuduga

Isyarat pertama ialah memilih struktur berdasarkan gabungan operasi. Median bergantung hanya pada bahagian tengah susunan tersusun, jadi mengekalkan susunan lengkap adalah tidak perlu. Untuk menjawab dalam O(1), satu atau dua calon tengah mesti sentiasa terdedah pada kedudukan yang boleh dibaca secara langsung. Bahagian atas heap menyediakan tepat akses sempadan itu.

Isyarat kedua ialah mengekalkan partition dan keseimbangan:

1. Max-heap lower menyimpan separuh lebih kecil, min-heap upper menyimpan separuh lebih besar, dan setiap nilai dalam lower adalah paling banyak setiap nilai dalam upper.
2. lower mempunyai saiz yang sama dengan upper atau tepat satu elemen tambahan.

Tiada satu syarat pun yang mencukupi secara bersendirian. Saiz yang serupa tidak menghalang nilai daripada ditempatkan di separuh yang salah. Susunan partition yang betul tidak menghalang satu heap daripada membesar jauh lebih besar, yang akan menyebabkan bahagian atasnya berhenti mewakili kedudukan tengah.

Isyarat ketiga ialah analisis kerumitan yang tepat. Sebuah kemasukan melakukan bilangan operasi heap yang malar, masing-masing O(log n). Sebuah pertanyaan membaca satu atau dua bahagian atas, jadi ia adalah O(1). Struktur masih menyimpan setiap input dan oleh itu menggunakan ruang O(n). "Penstriman" bermaksud kemas kini dalam talian di sini, bukan memori malar.

Akhirnya, penemuduga mencari pengesahan di luar sampel. Jawapan yang kukuh menguji elemen pertama, bilangan genap dan ganjil, pendua, semua nilai negatif, jujukan menaik dan menurun, serta had integer. Ia juga membandingkan jujukan operasi rawak dengan model senarai tersusun yang perlahan tetapi jelas betul.

Soalan Penjelasan Sebelum Menjawab

• Adakah hanya kemasukan sahaja, atau haruskah nilai lama dipadam? Dua heap biasa mencukupi untuk kemasukan sahaja. Tetingkap gelongsor memerlukan pemadaman malas atau multiset tertib.
• Bolehkah pertanyaan dijalankan pada aliran kosong? Arahan ini mengatakan tidak. API pengeluaran harus mengembalikan nilai pilihan atau membangkitkan ralat eksplisit sebagai ganti membaca bahagian atas yang kosong.
• Adakah input integer atau nilai titik terapung? Versi ini menggunakan integer. Jika NaN titik terapung dibenarkan, nilai-nilai tidak membentuk susunan jumlah normal, jadi semantik penolakan atau pemeringkatan mesti ditakrifkan.
• Bagaimana median ditakrifkan untuk bilangan genap? Arahan ini menggunakan purata aritmetik dua nilai tengah, jadi jenis pulangan mesti boleh mewakili pecahan.
• Mestikah keputusan tepat? Ya. Aliran tanpa sempadan di bawah bajet memori tetap memerlukan kontrak kuantil anggaran sebagai ganti.
• Bolehkah purata melimpah? Integer Python tidak melimpah. Bahasa lebar tetap harus menaikkan taraf kedua-dua operan sebelum penambahan dan pembahagian.
• Berapakah nisbah pertanyaan-kepada-kemasukan? Dua heap sesuai untuk pertanyaan yang kerap. Jika median hanya diminta sekali selepas semua input tiba, mengumpul dan mengisih biasanya lebih mudah.
• Adakah akses serentak diperlukan? Pelaksanaan ini adalah satu-benang. Versi serentak mesti memastikan pemindahan dan pertanyaan memerhati satu keadaan kedua-dua heap.

Rangka Kerja Jawapan 30 Saat

"Saya akan menyimpan separuh lebih kecil dalam max-heap bernama lower dan separuh lebih besar dalam min-heap bernama upper. Setiap nilai dalam lower mesti paling banyak setiap nilai dalam upper, dan lower mempunyai saiz yang sama atau satu elemen tambahan. Semasa kemasukan, saya mula-mula menolak ke dalam lower, memindahkan maksimumnya ke upper untuk memulihkan susunan partition, dan memindahkan minimum upper kembali jika upper menjadi lebih besar. Untuk bilangan ganjil, median ialah bahagian atas lower; untuk bilangan genap, ia adalah purata kedua-dua bahagian atas. Kemasukan menggunakan bilangan operasi heap O(log n) yang malar, pertanyaan adalah O(1), dan ruang adalah O(n)."

Penerokaan Mendalam Langkah demi Langkah

Langkah satu: bandingkan pendekatan asas dan kenal pasti kesesakan.

Carian binari mencari indeks kemasukan tatasusunan dalam O(log n), tetapi ia tidak menghapuskan kos anjakan O(n). Pokok seimbang biasa mengekalkan susunan, tetapi tanpa saiz subtree ia tidak dapat memilih elemen ke-k secara langsung. Dua heap hanya mengekalkan dua sempadan yang diperlukan untuk median, menjadikannya struktur lengkap terkecil untuk kontrak ini.

Langkah dua: tulis semula median sebagai satu atau dua bahagian atas heap.

Biar lower mengandungi separuh lebih kecil dalam max-heap, mendedahkan nilai terbesar separuh itu. Biar upper mengandungi separuh lebih besar dalam min-heap, mendedahkan nilai terkecil separuh itu. Benarkan lower mempunyai satu elemen tambahan:

Odd total:  lower has one extra, median = max(lower)
Even total: heaps have equal sizes, median = (max(lower) + min(upper)) / 2

Antara muka Python heapq yang tersedia secara meluas adalah berdasarkan min-heap. Untuk memastikan pelaksanaan mudah alih merentasi versi Python biasa, simpan nilai yang dinafikan dalam lower. Maksimum logik x menjadi nilai negatif terkecil yang disimpan -x, jadi -lower[0] adalah maksimum separuh bawah.

Langkah tiga: gunakan urutan tolak, pindah, dan imbang semula yang tetap.

Daripada bercabang ke setiap destinasi yang mungkin untuk nilai baharu, sentiasa:

1. Tolak num yang dinafikan ke dalam lower.
2. Pop maksimum logik lower dan tolak ke dalam upper.
3. Jika upper kini lebih besar, pindahkan minimumnya kembali ke lower.

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.lower = []  # Negated max-heap containing the smaller half
        self.upper = []  # Min-heap containing the larger half

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def find_median(self) -> float:
        if not self.lower:
            raise ValueError("median is undefined for an empty stream")

        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

Urutan ini melakukan pemindahan yang kelihatan berlebihan, tetapi ia menghapuskan beberapa kes yang mudah tersalah. Pelaksanaan lain yang sah membandingkan num dengan -lower[0], memilih heap, dan kemudian mengimbang semula. Kedua-duanya mempunyai kos asimptotik yang sama. Dalam temuduga, lebih suka versi yang invaryannya boleh anda buktikan dan semak dengan boleh dipercayai.

Langkah empat: buktikan invarian susunan.

Anggap sebelum kemasukan bahawa setiap nilai dalam lower adalah paling banyak setiap nilai dalam upper. Selepas nilai baharu ditolak sementara ke dalam lower, hanya nilai baharu itu sahaja yang mungkin berada di separuh yang salah. Pop maksimum lower yang dibesarkan:

• Setiap nilai yang tinggal dalam lower adalah paling banyak nilai yang di-pop.
• Setiap nilai lower lama sudah paling banyak setiap nilai upper lama.
• Oleh itu, selepas menambah maksimum yang di-pop ke dalam upper, setiap nilai lower baharu masih paling banyak setiap nilai upper baharu.

Selepas pemindahan itu, upper mungkin mempunyai satu elemen tambahan. Memindahkan minimumnya kembali ke lower mengekalkan susunan: nilai yang dipindahkan adalah paling banyak semua yang tinggal dalam upper dan tidak lebih kecil daripada sempadan bawah lama. Heap kemudiannya mempunyai saiz yang sama atau lower mempunyai satu elemen tambahan.

Kedua-dua invarian berlaku untuk dua heap kosong. Setiap kemasukan mengekalkannya, jadi secara induksi bahagian-bahagian atas mewakili kedudukan tengah selepas sebarang jujukan operasi.

Langkah lima: surih jujukan yang merentasi partition.

Insert 5:  lower = [5]       upper = []        median = 5
Insert 2:  lower = [2]       upper = [5]       median = 3.5
Insert 10: lower = [5, 2]    upper = [10]      median = 5
Insert 4:  lower = [4, 2]    upper = [5, 10]   median = 4.5

Tatasusunan sokongan heap tidak tersusun sepenuhnya. [4, 2] bermaksud hanya bahawa 4 adalah bahagian atas max-heap. Semakan nyahpepijat harus mengesahkan susunan heap, dua bahagian atas, dan invarian silang-heap daripada membandingkan tatasusunan sokongan sebagai senarai tersusun.

Langkah enam: kira kerumitan dan kenal pasti bila pendekatan lebih mudah menang.

add_num melakukan paling banyak lima tolak atau pop. Setiap operasi heap adalah O(log n), jadi bilangan malar kekal O(log n). find_median membaca panjang dan bahagian atas heap dalam O(1). Setiap nilai hidup dalam tepat satu heap, menghasilkan ruang O(n).

Jika sebuah produk mengumpul satu kelompok dan meminta satu median di penghujung, menyimpan dan mengisih tatasusunan adalah lebih ringkas dan mungkin mempunyai gelagat memori berterusan yang lebih baik. Mengekalkan struktur dalam talian adalah tidak perlu. Jika setiap nilai berada dalam julat tetap 0 hingga 100, tatasusunan 101 kiraan memberikan kemasukan O(1) dan imbasan 101 baldi tetap, juga malar untuk domain tetap itu.

Langkah tujuh: tutup gelung dengan kes deterministik dan ujian pembezaan rawak.

Sekurang-kurangnya, uji:

Untuk ujian rawak, tambah setiap integer yang dijana kepada kedua-dua MedianFinder dan tatasusunan rujukan. Isih rujukan dan kira bahagian tengahnya selepas setiap kemasukan. Bandingkan kedua-dua keputusan dan tegaskan bahawa len(lower) sama dengan len(upper) atau lebih satu. Model perlahan tidak sesuai untuk prestasi sasaran tetapi sangat baik sebagai oracle ketepatan.

Jawapan Sampel Berkualiti Tinggi

"Saya akan mengesahkan terlebih dahulu bahawa ini adalah median tepat masukan-sahaja dan bahawa pertanyaan tidak berlaku pada aliran kosong. Jika elemen tetingkap lama mesti dipadam, heap biasa tidak dapat mengalih keluar nilai arbitrari dengan cekap, jadi reka bentuk berubah.

Untuk pertanyaan masa malar, saya mahu bahagian tengah susunan tersusun sentiasa terdedah pada sempadan struktur. Saya akan menggunakan max-heap lower untuk separuh lebih kecil dan min-heap upper untuk separuh lebih besar. Dua invarian penting: setiap nilai dalam lower adalah paling banyak setiap nilai dalam upper, dan lower mempunyai saiz yang sama atau satu elemen tambahan.

Semasa kemasukan saya menggunakan urutan tiga langkah tetap. Tolak nilai baharu ke dalam lower, pindahkan maksimum lower ke upper untuk memulihkan partition, dan pindahkan minimum upper kembali jika upper menjadi lebih besar. Kedua-dua invarian kemudian berlaku semula. Dengan bilangan ganjil, lower mempunyai nilai tambahan dan bahagian atasnya adalah median. Dengan bilangan genap, saya puratakan kedua-dua bahagian atas.

Kemasukan melakukan bilangan operasi heap yang malar, jadi ia adalah O(log n). Pertanyaan membaca bahagian atas dalam O(1), dan mengekalkan setiap nilai memerlukan ruang O(n). Saya akan menguji satu elemen, bilangan genap, pendua, nilai negatif, input monotonik, dan had integer, kemudian menjalankan ujian pembezaan rawak terhadap model isih-setiap-langkah. Jika nilai terhad kepada 0 hingga 100, saya akan menggunakan 101 pembilang; jika hanya ada satu pertanyaan akhir, saya hanya akan mengisih."

Kesilapan Lazim

• Imbang hanya saiz heap → nilai boleh merentasi partition dan bahagian atas bukan dua nilai tengah → kekalkan kedua-dua invarian susunan dan saiz.
• Letak separuh lebih kecil dalam min-heap → bahagian atasnya adalah minimum global, bukan maksimum separuh bawah → gunakan max-heap untuk separuh lebih kecil.
• Kembalikan satu bahagian atas untuk bilangan genap → takrifan median salah → puratakan kedua-dua bahagian atas apabila saiz adalah sama.
• Tambah integer lebar tetap sebelum penukaran → dua nilai besar boleh melimpah terlebih dahulu → naikkan taraf kedua-dua operan sebelum menambah dan membahagi.
• Panggil kemasukan tatasusunan tersusun O(log n) → mencari indeks adalah pantas tetapi anjakan kekal O(n) → pisahkan kos carian daripada kos mutasi.
• Anggap tatasusunan heap Python sebagai tersusun sepenuhnya → tegasan nyahpepijat menjadi tidak sah → bergantung hanya pada akar dan sifat heap ibu bapa-anak.
• Baca indeks sifar daripada heap kosong → kegagalan berlaku pada sempadan yang tidak jelas → larang pertanyaan kosong atau kembalikan nilai pilihan secara eksplisit.
• Dakwa algoritma dalam talian menggunakan ruang malar → kedua-dua heap mengekalkan semua input → nyatakan ruang O(n) untuk median tepat.
• Guna semula kod yang sama untuk tetingkap gelongsor → nilai yang tamat tempoh boleh kekal di bahagian atas dan merosakkan keputusan → tambah pemadaman malas dan saiz sah, atau gunakan multiset tertib.
• Uji hanya sampel sahaja → pepijat penafian, pendua, dan imbang semula mungkin tidak tercetus → gabungkan kes tepi dengan ujian pembezaan rawak.

Soalan Susulan dan Respons

Susulan 1: Apakah yang berubah jika setiap integer berada antara 0 dan 100?

Simpan tatasusunan 101 kiraan dan jumlah bilangan elemen. Kemasukan menambah satu baldi dalam O(1). Untuk membuat pertanyaan, imbas baldi sehingga mencapai satu atau dua kedudukan tengah. Imbasan dan ruang adalah malar untuk domain tetap ini. Jika julat berkembang dengan input, imbasan adalah O(R) untuk saiz julat R dan tidak lagi harus digambarkan sebagai malar.

Susulan 2: Bagaimana jika 99% nilai berada antara 0 dan 100 tetapi selebihnya adalah arbitrari?

Kekalkan 101 pembilang untuk nilai dalam julat dan struktur statistik-tertib untuk nilai di bawah 0 dan di atas 100. Kiraan mereka menentukan sama ada kedudukan sasaran terletak dalam pencilan bawah, julat tetap, atau pencilan atas; kemudian pilih dalam struktur yang berkaitan. Heap biasa tidak menyokong pemilihan kedudukan arbitrari, jadi pernyataan 99% sahaja tidak membenarkan pertanyaan masa malar. Awalan bersifat adversarial masih boleh meletakkan kedudukan median di kalangan pencilan.

Susulan 3: Bagaimana anda mengira median bagi k nilai terbaru?

Pergerakan tetingkap memerlukan pemadaman nilai keluar. Heap binari tidak dapat mencari entri arbitrari dengan cekap. Penyelesaian biasa menambah peta kiraan pemadaman tertangguh dan menjejaki saiz sah untuk kedua-dua heap. Tandakan nilai keluar sebagai dipadam secara logik, dan pop secara fizikal hanya apabila ia mencapai bahagian atas; pangkas kedua-dua bahagian atas sebelum membaca median. Kemas kini adalah O(log k) diamortisasi, manakala carian bahagian atas kekal O(1). Multiset seimbang dengan sokongan pendua adalah lebih mudah apabila bahasa menyediakannya.

Susulan 4: Bolehkah algoritma memori tetap mengembalikan median tepat aliran tanpa sempadan?

Secara umum, tidak untuk aliran integer arbitrari. Nilai sejarah yang dibuang mungkin kemudiannya menentukan kedudukan tengah. Kontrak mesti berubah kepada kuantil anggaran, menggunakan lakaran kuantil dengan jaminan ralat kedudukan yang jelas, keperluan keyakinan, dan gelagat penggabungan. Itu adalah jawapan yang berbeza daripada struktur dua-heap tepat.

Susulan 5: Bagaimana anda menyokong kemasukan dan pertanyaan serentak?

Dua heap membentuk satu keadaan logik. Sambungan betul yang paling mudah melindungi operasi add_num dan find_median yang lengkap dengan mutex yang sama, menghalang pertanyaan daripada memerhati saat selepas nilai meninggalkan lower tetapi sebelum ia memasuki upper. Perkhidmatan yang berat dengan pembacaan boleh menerbitkan petikan median tak boleh ubah, tetapi selang petikan memperkenalkan pertukaran kesegaran yang perlu ada dalam kontrak API.

Susulan 6: Bolehkah median daripada beberapa serpihan digabungkan menjadi median global?

Tidak. Median serpihan kehilangan saiz dan taburan serpihan itu; malah purata berwajaran median serpihan bukan median global. Keputusan tepat memerlukan struktur yang boleh menjawab kedudukan global, seperti mengagregat kiraan ke atas domain terbatas dan melakukan pemilihan teragih. Keputusan anggaran boleh menggunakan ringkasan kuantil yang boleh digabungkan. Keperluan ketepatan dan kependaman mesti dipilih sebelum struktur global.