Wawancara koding: Mengimplementasikan weighted reservoir sampling

1. Petunjuk dan konteks

Setiap rekaman dalam suatu stream memiliki bobot positif, tetapi baik jumlah item maupun total bobot tidak diketahui. Implementasikan sampel berbobot berukuran k tanpa pengembalian: setiap rekaman muncul paling banyak satu kali, peluang inklusinya sebanding dengan bobotnya, dan stream dipindai tepat satu kali. Jelaskan pembuatan kunci (key generation), pemeliharaan kandidat, bobot ekstrem, dan pengujian distribusi.

2. Apa yang diuji oleh pewawancara

Apakah Anda membedakan antara pengambilan sampel dengan dan tanpa pengembalian serta memahami probabilitas yang sebanding dengan bobot.
Apakah Anda dapat mengubah pengambilan sampel berbobot menjadi mempertahankan k prioritas acak atau kunci eksponensial teratas.
Apakah Anda memilih min-heap berukuran k dan memberikan pembaruan O(log k) per rekaman.
Apakah Anda menangani bobot nol, sangat besar, atau sangat kecil, batas nilai acak, ID duplikat, dan seed yang dapat direproduksi.

3. Pertanyaan klarifikasi sebelum menjawab

Apakah bobot berupa bilangan positif berhingga, dan apakah rekaman berbobot nol harus dibuang atau dipertahankan?
Apakah pengambilan sampel dilakukan tanpa pengembalian, atau suatu rekaman boleh muncul lebih dari satu kali?
Apakah hanya sampel akhir yang diperlukan, atau setiap prefiks harus memiliki distribusi yang benar?
Apakah beberapa shard harus digabungkan, status (state) harus dipersistensikan, atau hasil harus dapat direproduksi secara persis?

4. Kerangka jawaban 30 detik

Hasilkan kunci acak independen untuk setiap rekaman berbobot w dan simpan k kunci terbesar. Bentuk yang stabil mengambil u secara seragam dari (0, 1] dan menghitung key = log(u) / w; karena kunci bernilai negatif, ini setara dengan menyimpan k kunci yang paling dekat dengan nol. Simpan sampel saat ini dalam min-heap berukuran k yang akarnya adalah kunci terkecil; ganti hanya jika kunci baru lebih besar. Satu kali pemindaian membutuhkan waktu O(n log k) dan ruang ekstra O(k). Validasi bobot dan buat sumber acak dapat diinjeksi (injectable).

5. Jawaban mendalam langkah demi langkah

Langkah 1: Tentukan distribusinya

Pengambilan sampel berbobot tanpa pengembalian bukanlah k penarikan independen dengan probabilitas w / total, karena hal itu dapat mengulang rekaman yang sama. Targetnya adalah himpunan berukuran k yang distribusi statistik urutannya sama dengan menarik item yang belum terpilih secara berulang sebanding dengan sisa bobotnya. Reservoir harus berupa sampel yang valid setelah setiap prefiks, tidak hanya setelah stream berakhir.

Langkah 2: Buat kunci yang stabil secara numerik

Perlombaan eksponensial (exponential race) memberikan implementasi yang praktis: ambil nilai acak seragam u dan hitung key = log(u) / w, lalu pertahankan kunci-kunci terbesar. Ketika u mendekati nol, log(u) menjadi lebih negatif; bobot yang lebih besar membuat kunci lebih dekat ke nol sehingga lebih mungkin masuk ke dalam top k. Hindari u ** (1 / w), yang dapat mengalami underflow atau kehilangan pemisahan presisi untuk bobot yang ekstrem.

text

sample_key(weight):
    require finite(weight) and weight > 0
    u = uniform_random_open_interval()
    return log(u) / weight

Langkah 3: Pertahankan top-k dengan min-heap

Simpan (key, sequence, item) di dalam heap, menggunakan urutan (sequence) untuk memecahkan hasil seri (tie) kunci yang sama persis. Lakukan push selama reservoir belum penuh. Setelah penuh, bandingkan kunci baru dengan root dan ganti hanya jika kunci baru lebih besar. Jika k bernilai nol, buang semua rekaman. Mengurutkan ulang larik (array) setelah setiap rekaman akan membuat pembaruan membutuhkan O(k log k), bukan O(log k).

Langkah 4: Tangani batasan input dan keacakan

Tolak NaN, tak terhingga, dan bobot negatif. Rekaman dengan bobot nol tidak dapat dipilih oleh sampel berbobot positif dan dapat dilewati. Sumber acak tidak boleh menghasilkan nol, atau log(0) menjadi tidak dapat digunakan; lakukan penarikan ulang atau batasi (clamp) ke nilai floating-point positif terkecil. Perlakukan ID duplikat sebagai rekaman terpisah kecuali masalah secara eksplisit meminta deduplikasi ID. Masukkan sumber pseudo-acak dalam pengujian agar kegagalan dapat direproduksi.

Langkah 5: Kompleksitas, validasi, dan ekstensi terdistribusi

Untuk n rekaman, implementasi mesin tunggal membutuhkan waktu O(n log k) dan ruang ekstra O(k). Gunakan simulasi Monte Carlo berbobot tetap untuk memeriksa bahwa inklusi marjinal meningkat seiring bertambahnya bobot, dan gunakan assertion untuk memastikan sampel tidak memiliki duplikat. Dalam stream terdistribusi, setiap shard dapat menghasilkan kunci dengan aturan yang sama dan koordinator dapat menggabungkan kandidat top-k shard; status, pembaruan, penghapusan, seed, dan biaya komunikasi tetap memerlukan perancangan eksplisit. Pengambilan sampel seragam secara langsung dari reservoir shard akan kehilangan informasi mengenai rekaman yang telah dibuang.

6. Contoh jawaban berkualitas tinggi

Untuk setiap rekaman berbobot positif, saya menghasilkan key = log(u) / w, di mana u berdistribusi seragam pada interval terbuka, dan mempertahankan k kunci terbesar. Kunci bernilai negatif, sehingga bobot yang lebih besar cenderung lebih dekat ke nol. Sebuah min-heap berkapasitas k menyimpan sampel; ketika penuh, kunci baru hanya akan menggantikan root terkecil jika nilainya lebih besar. Saya mendefinisikan perilaku untuk bobot tidak valid, nilai acak nol, k = 0, dan rekaman duplikat. Pemindaian memakan waktu O(n log k) dan ruang O(k). Saya memvalidasi distribusi dengan simulasi bobot tetap berulang dan menggabungkan kandidat terdistribusi menggunakan aturan kunci top-k global yang sama.

7. Kesalahan umum

Menarik secara independen dengan w / total → menghasilkan duplikat dan bukan pengambilan sampel tanpa pengembalian → gunakan kunci acak dan top-k.
Menghitung u ** (1 / w) secara langsung → underflow untuk bobot ekstrem → bandingkan kunci logaritmik.
Menggunakan max-heap untuk top-k → memerlukan pencarian nilai terkecil → gunakan min-heap sehingga titik penggantian adalah root.
Mengizinkan u = 0 → log(0) menjadi tak terhingga negatif → gunakan sumber interval terbuka atau tarik ulang.
Hanya menguji satu output → melewatkan bias jangka panjang → jalankan uji Monte Carlo bobot tetap dan pastikan tidak ada duplikat.

8. Pertanyaan lanjutan dan tanggapan

Mengapa key = log(u) / w menghasilkan weighted sampling?

Perlakukan -log(u) sebagai variabel eksponensial dengan laju satu. Membaginya dengan w memberikan waktu eksponensial dengan laju w. Waktu eksponensial terkecil lebih mungkin berasal dari laju yang lebih besar; menegatifkannya berarti mempertahankan kunci terbesar, yang menghasilkan pengambilan sampel berbobot tanpa pengembalian.

Bagaimana cara membuat hasil dapat direproduksi?

Injeksi sumber pseudo-acak dengan seed eksplisit dan catat pengidentifikasi item, versi bobot, serta versi algoritma dalam metadata eksperimen. Jangan bergantung pada penjadwalan thread atau status acak global, karena input yang identik dapat menghasilkan sampel yang berbeda.

Bisakah dua reservoir yang sudah terbentuk digabungkan?

Jika kedua shard menghasilkan kunci independen berdasarkan aturan yang sama, gabungkan kunci kandidat keduanya dan ambil k teratas secara global. Memperlakukan hanya dua reservoir akhir sebagai data biasa dan mengambil sampel lagi akan menghilangkan informasi tentang rekaman yang dibuang. Kunci yang dipersistensikan serta pembaruan atau penghapusan shard juga memerlukan perilaku yang terdefinisi.

Bagaimana jika bobot berubah seiring waktu?

Mengubah bobot akan mengubah distribusi target, sehingga kunci lama tidak lagi mewakili bobot baru. Buat ulang kunci untuk rekaman yang terpengaruh atau masukkan kembali event dengan versi bobot baru ke dalam stream. Nyatakan apakah perkiraan jangka pendek dapat diterima dan bagaimana sampel lama dipensiunkan (dihentikan penggunaannya).

Wawancara koding: Mengimplementasikan weighted reservoir sampling

Pertanyaan