Wawancara Koding: Menemukan Median dari Aliran Data (Data Stream)

Masalah dan Konteks yang Berlaku

Rancang MedianFinder dengan dua operasi:

• addNum(num) menambahkan integer ke dalam stream.
• findMedian() mengembalikan median dari setiap nilai yang telah masuk sejauh ini. Jika jumlah elemen ganjil, kembalikan nilai tengah; jika jumlah elemen genap, kembalikan rata-rata dari dua nilai tengah.

Asumsikan hanya ada operasi penyisipan tanpa penghapusan, dan findMedian() hanya dipanggil setelah setidaknya ada satu penyisipan. Input dapat mencakup bilangan negatif, duplikat, dan signed 32-bit integer, dengan paling banyak 50.000 operasi. Targetnya adalah O(log n) per penyisipan, O(1) per kueri, dan memori O(n).

Sebagai contoh, setelah menyisipkan 5, 2, 10, 4, median berjalannya adalah 5, 3.5, 5, 4.5. Melakukan sorting pada setiap kueri memang benar tetapi memakan biaya O(n log n) per kueri. Menjaga array tetap terurut sepenuhnya membuat kueri bernilai O(1), namun menyisipkan elemen di tengah tetap menggeser O(n) elemen.

Materi persiapan wawancara publik pada tahun 2026 terus menampilkan ini sebagai masalah koding representatif untuk teknik two-heaps. Masalah ini berlaku untuk sesi wawancara koding software general, backend, data, dan infrastruktur. Sinyal kompetensi yang dicari bukanlah sekadar mengingat frasa “max-heap plus min-heap”, melainkan menurunkan struktur data dari kebutuhan kueri, menyatakan kedua invarian, dan membuktikan mengapa urutan transfer yang tetap dapat menjaga partisi data.

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah pemilihan struktur data berdasarkan bauran operasi. Median hanya bergantung pada bagian tengah dari data yang terurut, sehingga mempertahankan urutan lengkap tidaklah perlu. Untuk menjawab dalam O(1), satu atau dua kandidat tengah harus selalu berada di posisi yang dapat langsung dibaca. Elemen teratas heap (heap top) menyediakan akses batas tersebut secara tepat.

Sinyal kedua adalah mempertahankan partisi sekaligus keseimbangan:

1. Max-heap lower menyimpan paruh yang lebih kecil, min-heap upper menyimpan paruh yang lebih besar, dan setiap

nilai dalam lower bernilai kurang dari atau sama dengan setiap nilai dalam upper.

1. lower memiliki ukuran yang sama dengan upper atau memiliki tepat satu elemen ekstra.

Salah satu kondisi saja tidak cukup. Ukuran yang seimbang tidak menjamin elemen berada di paruh yang benar. Partisi yang benar juga tidak mencegah salah satu heap tumbuh jauh lebih besar, yang dapat menyebabkan elemen teratasnya bukan lagi representasi nilai tengah.

Sinyal ketiga adalah ketepatan analisis kompleksitas. Sebuah penyisipan menjalankan sejumlah operasi heap yang konstan, masing-masing bernilai O(log n). Sebuah kueri membaca satu atau dua elemen teratas, sehingga bernilai O(1). Struktur ini tetap menyimpan setiap input dan karenanya menggunakan ruang O(n). Istilah “streaming” di sini mengacu pada pembaruan secara online, bukan penggunaan memori konstan.

Terakhir, pewawancara mencari validasi di luar contoh standar. Jawaban yang kuat menguji elemen pertama, jumlah elemen genap dan ganjil, data duplikat, nilai serba negatif, urutan menaik dan menurun, serta nilai integer ekstrem. Jawaban tersebut juga membandingkan urutan operasi acak terhadap model daftar terurut (sorted list) yang lambat tetapi jelas benar.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah operasinya hanya penyisipan, atau nilai lama harus dihapus? Dua heap biasa sudah cukup untuk operasi yang hanya menyisipkan. Sliding window membutuhkan lazy deletion atau ordered multiset.
• Bisakah kueri dijalankan pada stream yang kosong? Prompt ini menyatakan tidak. API produksi sebaiknya mengembalikan nilai opsional (optional) atau memunculkan error eksplisit daripada membaca elemen teratas dari heap kosong.
• Apakah input berupa integer atau bilangan floating-point? Versi ini menggunakan integer. Jika floating-point NaN diizinkan, nilai-nilai tersebut tidak membentuk urutan total (total order) normal, sehingga semantik penolakan atau pengurutan harus didefinisikan.
• Bagaimana median didefinisikan untuk jumlah elemen genap? Prompt ini menggunakan rata-rata aritmatika dari dua nilai tengah, sehingga tipe kembalian harus dapat merepresentasikan pecahan.
• Haruskah hasilnya eksak? Ya. Stream tak terbatas dengan batasan memori tetap memerlukan kontrak perkiraan kuantil (approximate quantile).
• Bisakah perhitungan rata-rata menyebabkan overflow? Integer pada Python tidak mengalami overflow. Bahasa dengan tipe data fixed-width harus mempromosikan kedua operan sebelum penjumlahan dan pembagian.
• Berapa rasio antara kueri dan penyisipan? Pendekatan dua heap cocok untuk kueri yang sering. Jika median hanya diminta sekali setelah semua input masuk, mengumpulkan data dan melakukan sorting biasanya lebih sederhana.
• Apakah akses konkuren diperlukan? Implementasi ini bersifat single-threaded. Versi konkuren harus memastikan transfer dan kueri membaca satu state yang konsisten dari kedua heap.

Kerangka Jawaban 30 Detik

“Saya akan menyimpan paruh yang lebih kecil dalam sebuah max-heap bernama lower dan paruh yang lebih besar dalam sebuah min-heap bernama upper. Setiap nilai dalam lower harus kurang dari atau sama dengan setiap nilai dalam upper, dan lower memiliki ukuran yang sama atau memiliki tepat satu elemen lebih banyak. Saat penyisipan, saya pertama-tama memasukkannya ke lower, memindahkan nilai maksimumnya ke upper untuk memulihkan urutan partisi, dan memindahkan kembali nilai minimum dari upper jika upper menjadi lebih besar. Untuk jumlah ganjil, median adalah elemen teratas dari lower; untuk jumlah genap, median adalah rata-rata dari kedua elemen teratas. Penyisipan menggunakan sejumlah operasi heap O(log n) yang konstan, kueri membutuhkan O(1), dan ruang memori adalah O(n).”

Pembahasan Mendalam Langkah demi Langkah

Langkah satu: bandingkan pendekatan dasar dan temukan bottleneck-nya.

Binary search dapat menemukan indeks penyisipan array dalam waktu O(log n), tetapi tidak menghilangkan biaya pergeseran elemen sebesar O(n). Balanced tree biasa menjaga urutan elemen, tetapi tanpa ukuran subtree ia tidak dapat memilih elemen ke-k secara langsung. Dua heap hanya mempertahankan dua batas yang diperlukan untuk median, menjadikannya struktur data lengkap terkecil untuk kontrak kebutuhan ini.

Langkah dua: nyatakan ulang median sebagai satu atau dua elemen teratas heap.

Biarkan lower memuat paruh yang lebih kecil dalam max-heap, yang memperlihatkan nilai terbesar dari paruh tersebut. Biarkan upper memuat paruh yang lebih besar dalam min-heap, yang memperlihatkan nilai terkecil dari paruh tersebut. Izinkan lower memiliki satu elemen ekstra:

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

Antarmuka heapq bawaan Python berbasis min-heap. Agar implementasi tetap portabel di berbagai versi Python standar, simpan nilai-nilai dalam bentuk negatif di lower. Nilai maksimum logis x menjadi nilai negatif terkecil yang disimpan -x, sehingga -lower[0] adalah nilai maksimum dari paruh bawah.

Langkah tiga: gunakan urutan push, transfer, dan rebalance yang tetap.

Daripada membuat percabangan logika untuk setiap kemungkinan tujuan penempatan nilai baru, lakukan langkah berikut secara konsisten:

1. Push nilai negatif num ke dalam lower.
2. Pop nilai maksimum logis dari lower dan lakukan push ke upper.
3. Jika upper sekarang berukuran lebih besar, pindahkan nilai 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 tampaknya melakukan satu kali transfer ekstra, tetapi berhasil menghilangkan beberapa penanganan kasus percabangan yang rawan bug. Implementasi valid lainnya membandingkan num dengan -lower[0], memilih heap yang sesuai, lalu melakukan rebalance. Keduanya memiliki kompleksitas asimtotik yang sama. Dalam wawancara, pilihlah versi yang invarian-nya dapat Anda buktikan dan tinjau dengan percaya diri.

Langkah empat: buktikan invarian urutan.

Asumsikan sebelum penyisipan bahwa setiap nilai dalam lower bernilai kurang dari atau sama dengan setiap nilai dalam upper. Setelah nilai baru di-push sementara ke lower, hanya nilai baru tersebut yang berpotensi berada di paruh yang salah. Lakukan pop pada nilai maksimum dari lower yang telah membesar:

• Setiap nilai yang tersisa di lower bernilai kurang dari atau sama dengan nilai yang di-pop.
• Setiap nilai lama di lower sudah pasti bernilai kurang dari atau sama dengan setiap nilai lama di upper.
• Oleh karena itu, setelah menambahkan nilai maksimum yang di-pop ke upper, setiap nilai baru di lower tetap kurang dari atau sama dengan

setiap nilai baru di upper.

Setelah transfer tersebut, upper mungkin memiliki satu elemen ekstra. Memindahkan nilai minimumnya kembali ke lower tetap menjaga urutan: nilai yang dipindahkan bernilai kurang dari atau sama dengan semua elemen yang tersisa di upper dan tidak lebih kecil dari batas bawah yang lama. Ukuran kedua heap kemudian menjadi sama besar atau lower memiliki satu elemen ekstra.

Kedua invarian tersebut berlaku untuk dua heap kosong. Karena setiap penyisipan mempertahankan kedua kondisi ini, melalui induksi matematika elemen teratas selalu merepresentasikan posisi tengah setelah urutan operasi apa pun.

Langkah lima: telusuri urutan yang melintasi partisi.

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

Array dasar (backing array) sebuah heap tidak sepenuhnya terurut. [4, 2] hanya bermakna bahwa 4 adalah elemen teratas max-heap. Pengecekan debugging harus memverifikasi properti heap, kedua elemen teratas, dan invarian lintas-heap, bukan membandingkan array dasarnya seolah-olah sebagai list yang terurut.

Langkah enam: hitung kompleksitas dan kenali kapan pendekatan yang lebih sederhana lebih unggul.

add_num menjalankan paling banyak lima operasi push atau pop. Setiap operasi heap bernilai O(log n), sehingga sejumlah konstan operasi heap tetap bernilai O(log n). find_median membaca panjang array dan elemen teratas heap dalam O(1). Setiap nilai berada di tepat satu heap, menghasilkan kebutuhan ruang O(n).

Jika suatu produk mengumpulkan data dalam satu batch dan hanya meminta satu kali nilai median di akhir, menyimpan dan mengurutkan array menghasilkan kode yang lebih ringkas dan memiliki perilaku contiguous-memory yang lebih baik. Mempertahankan struktur data online menjadi tidak perlu. Jika setiap nilai berada dalam rentang tetap dari 0 hingga 100, array berisi 101 count memberikan penyisipan O(1) dan pemindaian terhadap 101 bucket tetap, yang juga konstan untuk domain tetap tersebut.

Langkah tujuh: tutup pembahasan dengan kasus uji deterministik dan randomized differential testing.

Minimal, ujilah skenario berikut:

Untuk pengujian acak (randomized test), tambahkan setiap integer yang di-generate ke MedianFinder dan ke sebuah reference array. Lakukan sorting pada reference array dan hitung nilai tengahnya setelah setiap penyisipan. Bandingkan kedua hasil dan pastikan melalui assertion bahwa len(lower) sama dengan len(upper) atau satu lebih besar. Model yang lambat ini tidak cocok untuk target performa produksi, tetapi sangat ideal sebagai correctness oracle.

Contoh Jawaban Berkualitas Tinggi

“Pertama-tama saya akan mengonfirmasi bahwa ini adalah pencarian median eksak untuk stream yang hanya mendukung penyisipan, dan kueri tidak akan dipanggil pada stream yang kosong. Jika elemen jendela lama harus dihapus, heap biasa tidak dapat menghapus nilai arbitrer secara efisien, sehingga rancangannya akan berbeda.

Untuk kueri dengan waktu konstan, saya ingin bagian tengah dari urutan data yang terurut selalu tersedia pada batas struktur data. Saya akan menggunakan max-heap lower untuk paruh yang lebih kecil dan min-heap upper untuk paruh yang lebih besar. Dua invarian penting adalah: setiap nilai di lower bernilai kurang dari atau sama dengan setiap nilai di upper, dan lower memiliki ukuran yang sama atau tepat satu lebih besar.

Saat penyisipan, saya menggunakan urutan tiga langkah yang tetap. Push nilai baru ke lower, pindahkan nilai maksimum lower ke upper untuk memulihkan partisi, lalu pindahkan nilai minimum upper kembali jika upper menjadi lebih besar. Kedua invarian akan kembali terpenuhi. Jika jumlah total ganjil, lower memegang elemen ekstra tersebut dan elemen teratasnya adalah median. Jika genap, saya menghitung rata-rata dari kedua elemen teratas.

Penyisipan melakukan sejumlah operasi heap yang konstan, sehingga kompleksitasnya adalah O(log n). Kueri membaca elemen teratas dalam O(1), dan menyimpan semua nilai membutuhkan memori O(n). Saya akan menguji kasus satu elemen, jumlah genap, duplikat, nilai negatif, input monotonik, dan nilai ekstrem integer, lalu menjalankan randomized differential test terhadap model sort-on-every-step. Jika nilai dibatasi dari 0 hingga 100, saya akan menggunakan 101 counter; jika hanya ada satu kueri di akhir, saya cukup melakukan sorting biasa.”

Kesalahan Umum

• Hanya menyeimbangkan ukuran heap → nilai dapat melompati partisi sehingga elemen teratas bukanlah dua nilai tengah → pertahankan invarian urutan dan invarian ukuran sekaligus.
• Menaruh paruh yang lebih kecil di min-heap → elemen teratasnya adalah nilai minimum global, bukan maksimum dari paruh bawah → gunakan max-heap untuk paruh yang lebih kecil.
• Mengembalikan satu elemen teratas saat jumlahnya genap → definisi median menjadi salah → hitung rata-rata kedua elemen teratas saat ukurannya sama.
• Menjumlahkan integer fixed-width sebelum konversi tipe → dua nilai besar dapat memicu overflow terlebih dahulu → promosikan kedua operan sebelum melakukan penjumlahan dan pembagian.
• Menyebut penyisipan pada sorted array bernilai O(log n) → pencarian indeks memang cepat tetapi pergeseran data tetap membutuhkan O(n) → pisahkan biaya pencarian dari biaya mutasi array.
• Menganggap array heap pada Python terurut sepenuhnya → assertion debugging menjadi tidak valid → hanya bergantung pada root dan properti relasi parent-child pada heap.
• Membaca indeks nol dari heap yang kosong → error terjadi di batas yang tidak jelas → larang kueri saat kosong atau kembalikan nilai opsional secara eksplisit.
• Mengklaim algoritma online ini menggunakan memori konstan → kedua heap tetap menyimpan seluruh input → nyatakan ruang memori O(n) untuk median eksak.
• Menggunakan kembali kode yang sama untuk sliding window → elemen yang sudah kedaluwarsa bisa tetap berada di elemen teratas dan merusak hasil → tambahkan lazy deletion dan pelacakan ukuran valid, atau gunakan ordered multiset.
• Hanya menguji contoh dasar → bug terkait negasi, duplikat, dan rebalancing mungkin tidak terdeteksi → gabungkan edge case dengan randomized differential testing.

Pertanyaan Lanjutan dan Jawabannya

Lanjutan 1: Apa yang berubah jika setiap integer berada di antara 0 dan 100?

Gunakan array berisi 101 counter dan variabel total hitungan elemen. Operasi penyisipan menambahkan satu bucket dalam O(1). Untuk kueri, pindai bucket sampai mencapai satu atau dua peringkat tengah. Waktu pemindaian dan memori bersifat konstan untuk domain yang tetap ini. Jika rentang nilai membesar seiring pertumbuhan input, waktu pemindaian adalah O(R) untuk ukuran rentang R dan tidak boleh lagi disebut konstan.

Lanjutan 2: Bagaimana jika 99% nilai berada di antara 0 dan 100 tetapi sisanya arbitrer?

Gunakan 101 counter untuk nilai dalam rentang tersebut dan struktur data order-statistic untuk nilai di bawah 0 dan di atas 100. Jumlah elemennya menentukan apakah peringkat target berada di outlier bawah, rentang tetap, atau outlier atas; kemudian lakukan pemilihan di dalam struktur yang relevan. Heap biasa tidak mendukung pencarian peringkat arbitrer, sehingga pernyataan 99% saja tidak menjamin kueri konstan. Prefiks input yang dirancang khusus (adversarial) tetap dapat menempatkan median di antara nilai-nilai outlier.

Lanjutan 3: Bagaimana cara menghitung median dari k nilai terakhir?

Pergeseran jendela (window) mengharuskan penghapusan nilai yang keluar. Binary heap tidak dapat menemukan elemen arbitrer secara efisien. Solusi umum adalah menambahkan map pencatat delayed-deletion dan melacak ukuran valid dari kedua heap. Tandai nilai yang keluar sebagai terhapus secara logis, dan lakukan pop secara fisik hanya ketika elemen tersebut mencapai posisi teratas heap; bersihkan kedua elemen teratas sebelum membaca median. Operasi pembaruan bernilai amortized O(log k), sementara pembacaan median tetap bernilai O(1). Penggunaan balanced multiset yang mendukung duplikat menjadi solusi yang lebih sederhana jika bahasa pemrograman menyediakannya.

Lanjutan 4: Bisakah algoritma memori-konstan mengembalikan median eksak dari stream tak terbatas?

Secara umum tidak bisa untuk stream integer arbitrer. Nilai historis yang dibuang suatu saat bisa saja menjadi penentu posisi tengah. Kontrak masalah harus diubah menjadi kuantil perkiraan (approximate quantile), menggunakan quantile sketch dengan garansi rank-error eksplisit, kebutuhan tingkat keyakinan (confidence), dan perilaku penggabungan (merge). Itu adalah pendekatan yang berbeda dari struktur dua heap eksak.

Lanjutan 5: Bagaimana cara mendukung operasi penyisipan dan kueri yang konkuren?

Kedua heap membentuk satu kesatuan state logis. Ekstensi sederhana yang benar adalah melindungi seluruh operasi add_num dan find_median dengan mutex yang sama, mencegah kueri membaca state tepat setelah elemen keluar dari lower namun sebelum masuk ke upper. Layanan dengan beban baca tinggi dapat mempublikasikan snapshot median yang immutable, tetapi interval pembuatan snapshot memperkenalkan trade-off pada tingkat kesegaran data (freshness) yang harus didefinisikan dalam kontrak API.

Lanjutan 6: Bisakah median dari beberapa shard digabungkan menjadi median global?

Tidak bisa. Nilai median shard kehilangan informasi ukuran dan distribusi dari shard asalnya; bahkan rata-rata tertimbang dari median setiap shard bukanlah median global. Hasil yang eksak memerlukan struktur yang dapat menjawab peringkat global, seperti mengagregasi frekuensi pada domain terbatas dan melakukan seleksi terdistribusi. Hasil perkiraan dapat menggunakan mergeable quantile summary. Kebutuhan presisi dan latensi harus ditentukan sebelum memilih arsitektur global tersebut.