Wawancara coding: Bagaimana cara mengambil sampel secara seragam dari stream dengan panjang yang tidak diketahui?

Pertanyaan dan use case

Anda hanya dapat membaca stream satu kali; panjangnya n tidak diketahui, dan Anda memerlukan k item berbeda dengan probabilitas yang sama. Anda tidak dapat menyimpan stream atau menunggu indeks acak akhir. Reservoir sampling mempertahankan reservoir tetap berukuran k: ketika item i tiba, item tersebut masuk dengan probabilitas k/i dan menggantikan slot reservoir yang dipilih secara seragam.

Pertanyaan ini menguji algoritma streaming teracak. Makalah Vitter mempelajari pengambilan sampel satu lintasan ketika ukuran populasi tidak diketahui, dan catatan kuliah universitas memberikan induksi keseragaman. Kategori utamanya adalah coding: invarian probabilitas di bawah batas memori, bukan implementasi platform data.

Hal yang dievaluasi pewawancara

• Apakah Anda mengenali pola reservoir dengan ukuran tidak diketahui, satu lintasan, dan memori tetap.
• Apakah Anda menjelaskan aturan penggantian k=1 1/i sebelum menggeneralisasi ke k.
• Apakah Anda membuktikan bahwa setelah item i, setiap item memiliki probabilitas k/i di dalam sampel.
• Apakah Anda menghindari sampel duplikat, asumsi keliru bahwa n diketahui, dan integer acak yang bias.
• Apakah Anda menyatakan waktu O(n), ruang O(k), dan batasan weighted sampling.

Klarifikasi sebelum menjawab

• Apakah k berupa integer positif? Apa yang harus terjadi untuk k <= 0 atau item stream yang kurang dari k?
• Apakah "berbeda" berarti rekaman yang berbeda atau deduplikasi berdasarkan nilai?
• Bisakah stream kosong, tak terbatas, atau terputus? Output dan pemulihannya berbeda.
• Apakah reservoir akhir merupakan satu-satunya output, atau harus dapat diamati selama pemindaian?
• Apakah API acak menyediakan integer yang tidak bias pada rentang yang diperlukan?
• Apakah targetnya seragam atau berbobot/bertingkat? Weighted sampling memerlukan invarian yang berbeda.

Kerangka jawaban 30 detik

"Isi reservoir dengan k item pertama. Untuk item i, dimulai dari satu, hasilkan integer tidak bias j di [0, i-1]. Jika j < k, ganti reservoir[j]; jika tidak, buang item tersebut. Setelah item i, setiap item memiliki probabilitas k/i: item baru masuk dengan k/i, dan item lama bertahan dengan k/(i-1) dikali 1 - 1/i. Algoritma ini berjalan dalam satu lintasan, waktu O(n), dan ruang ekstra O(k)."

Jawaban mendalam langkah demi langkah

Langkah 1: Mulai dengan k=1.

Simpan item pertama. Untuk item i, ganti kandidat saat ini dengan probabilitas 1/i. Setelah memproses i item, masing-masing memiliki probabilitas 1/i untuk dipertahankan.

Langkah 2: Generalisasi ke k.

Isi k slot pertama. Untuk item i, masuk dengan probabilitas k/i; jika masuk, pilih salah satu dari k slot secara seragam. Sebuah integer j di [0, i-1] mengimplementasikan ini: j < k berarti mengganti slot j.

Langkah 3: Tulis pseudocode.

reservoir = first k items
for i = k+1 .. n:
  j = uniformInteger(0, i-1)
  if j < k:
    reservoir[j] = item i
return reservoir

Jika stream tidak dapat diisi sebelumnya, tambahkan selama seen <= k, lalu gunakan percabangan yang sama. Generator integer harus mencakup seluruh rentang tanpa bias.

Langkah 4: Buktikan probabilitas item baru.

Pada item i, probabilitas penyertaannya adalah k/i. Setelah disertakan, item tersebut bertahan di setiap langkah berikutnya dengan probabilitas ∏(1 - 1/t) = i/n, karena slot tertentu diganti dengan probabilitas 1/t. Oleh karena itu, probabilitas akhirnya adalah k/i × i/n = k/n.

Langkah 5: Buktikan probabilitas item lama.

Asumsikan setiap item lama memiliki probabilitas k/(i-1) setelah item i-1. Pada langkah i, item tersebut diganti dengan probabilitas k/i × 1/k = 1/i, sehingga bertahan dengan 1 - 1/i. Probabilitas barunya adalah k/(i-1) × (i-1)/i = k/i. Item baru dan lama memenuhi invarian yang sama.

Langkah 6: Analisis kompleksitas dan pembuatan angka acak.

Setiap item diproses satu kali: waktu O(n). Reservoir menampung k item: ruang ekstra O(k). Untuk hitungan di luar presisi integer yang aman, gunakan API integer tidak bias yang mendukung rentang yang diperlukan.

Langkah 7: Tangani batasan input.

Stream kosong mengembalikan sampel kosong. k = 0 mengembalikan sampel kosong atau memunculkan error yang terdokumentasi. Jika kurang dari k item tiba, kembalikan item aktual atau gagalkan sesuai kontrak. Deduplikasi berdasarkan nilai membutuhkan state tambahan dan dapat melanggar O(k).

Langkah 8: Jelaskan ekstensi terbobot dan terdistribusi.

Weighted sampling mengubah distribusi target, sehingga penggantian dengan probabilitas yang sama menjadi tidak valid; diskusikan kunci weighted-reservoir seperti Efraimidis–Spirakis. Reservoir terdistribusi memerlukan jumlah hitungan dan prioritas/bobot untuk digabungkan dengan benar; menggabungkan sampel shard secara langsung menyebabkan bias.

Contoh jawaban berkualitas tinggi

"Saya mempertahankan reservoir berkapasitas k. Mengisinya dengan k item pertama. Mulai dari item i = k+1 dan seterusnya, ambil integer tidak bias j di [0, i-1]; jika j < k, ganti slot j, jika tidak, buang. Item baru masuk dengan probabilitas k/i. Item lama tertentu diganti dengan probabilitas 1/i, sehingga probabilitasnya berubah dari k/(i-1) menjadi k/(i-1) × (1-1/i) = k/i. Berdasarkan induksi, setiap item memiliki probabilitas akhir k/n. Algoritma ini berjalan dalam satu lintasan, waktu O(n), dan ruang O(k). Saya menguji input kosong, k=1, k=0, rekaman berulang, simulasi berulang, dan menurunkan kembali invarian secara eksplisit untuk varian terbobot atau terdistribusi."

Kesalahan umum

• Menyimpan seluruh stream terlebih dahulu → melanggar batasan ukuran tidak diketahui dan memori → perbarui reservoir secara online.
• Menggunakan 1/k untuk setiap item baru → probabilitas tidak beradaptasi dengan i → gunakan k/i.
• Menggunakan random() % i → operasi modulo dapat menyebabkan bias → gunakan pengambilan sampel integer yang tidak bias.
• Memilih slot pengganti secara tidak seragam → beberapa kombinasi menjadi lebih mungkin terpilih → pilih di antara k slot secara seragam.
• Menggunakan k/n saat memindai → n tidak diketahui dan probabilitas berubah di setiap langkah → gunakan hitungan saat ini i.
• Mengabaikan semantik duplikat → rekaman berbeda dan nilai berbeda adalah hal yang berbeda → perjelas deduplikasi terlebih dahulu.
• Menggabungkan (concatenate) reservoir shard → ukuran shard yang tidak sama membiaskan hasil → gabungkan dengan hitungan dan prioritas.
• Menggunakan kembali algoritma seragam untuk pembobotan → distribusi target telah berubah → gunakan weighted reservoir sampling dengan pembuktian baru.

Pertanyaan lanjutan dan jawabannya

Pertanyaan lanjutan 1: Mengapa probabilitas penggantian item baru adalah k/i?

Pada item i, algoritma memilih salah satu dari i posisi secara seragam. Sebanyak k posisi pertama mewakili reservoir, sehingga peluang mengenai salah satunya adalah k/i.

Pertanyaan lanjutan 2: Bagaimana Anda membuktikan keadilan untuk k=1?

Item pertama disimpan dengan probabilitas satu. Item i menggantikannya dengan 1/i; setiap item lama bertahan dengan (1/(i-1)) × (1-1/i) = 1/i, yang menghasilkan induksi.

Pertanyaan lanjutan 3: Bagaimana cara menghasilkan integer yang tidak bias?

Gunakan API uniform-integer, atau rejection sampling yang membuang nilai acak di luar rentang terbesar yang habis dibagi. Jangan berasumsi bahwa modulo sederhana selalu bebas dari bias.

Pertanyaan lanjutan 4: Bagaimana jika stream berakhir sebelum k item?

Kembalikan item aktual atau munculkan error yang terdokumentasi. Jangan pernah mengarang entri; nyatakan perilakunya sebelum menulis kode.

Pertanyaan lanjutan 5: Bagaimana cara mengambil sampel dengan bobot?

Tentukan distribusi target terbobot, lalu gunakan kunci acak weighted-reservoir atau transformasi eksponensial/logaritmik. Bukti seragam k/i tidak lagi berlaku secara langsung.

Pertanyaan lanjutan 6: Bagaimana cara menggabungkan reservoir terdistribusi?

Setiap shard membawa jumlah itemnya serta informasi prioritas acak atau bobot yang cukup. Gabungkan sesuai dengan aturan pengambilan sampel global; penggabungan langsung atau pemotongan acak akan menguntungkan shard yang lebih kecil.

Pertanyaan lanjutan 7: Bagaimana cara memvalidasi keseragaman?

Jalankan banyak percobaan pada stream pendek yang tetap, bandingkan frekuensi penyertaan setiap item dengan k/n, serta uji batasan dan seed yang dapat direproduksi. Statistik dapat mengungkap bias, tetapi tidak menggantikan pembuktian probabilitas.