Wawancara koding: Bagaimana cara mengimplementasikan pengacakan array in-place yang seragam?

Masalah dan konteks

Implementasikan reset() untuk memulihkan urutan asli dan shuffle() untuk mengembalikan permutasi acak yang seragam. Pertanyaan ini menguji algoritma teracak, swap in-place, batas angka acak, dan kemampuan pengujian (testability); pola yang sama muncul dalam sampling, pengundian lot, dan test fixtures.

Apa yang diuji oleh pewawancara

• Memilih Fisher–Yates daripada menukar posisi acak arbitrer secara berulang-ulang.
• Mengambil sampel indeks i hanya dari bagian yang belum ditetapkan (fixed).
• Membedakan antara API acak inklusif dan setengah terbuka (half-open) untuk menghindari bias atau overflow.
• Menjaga baseline yang tidak dapat diubah (immutable) sehingga reset() tidak terpengaruh oleh pengacakan.
• Menjelaskan waktu O(n), ruang ekstra O(1), dan keseragaman (uniformity).
• Mendiskusikan PRNG dengan seed, array kosong, nilai duplikat, dan batas uji statistik.

Pertanyaan klarifikasi yang perlu diajukan

• Apakah shuffle() harus mengembalikan array baru atau mengubah dan mengembalikan array kerja?
• Haruskah reset() mengembalikan salinan defensif sehingga pemanggil tidak dapat mengubah status internal?
• Apakah sumber acak dapat diinjeksi, atau apakah diperlukan sumber yang aman secara kriptografis?
• Apakah nilai duplikat diperbolehkan, dan apakah nilai yang sama pada posisi berbeda dianggap sebagai permutasi yang berbeda?
• Apakah kita memerlukan thread safety, seed yang dapat direproduksi, atau ketidakpastian kriptografis?
• Apakah input memerlukan streaming atau ruang pembantu konstan?

Kerangka jawaban 30 detik

“Saya menyimpan snapshot asli dan array kerja. Untuk i dari indeks terakhir turun ke satu, saya mengambil sampel j yang seragam di [0, i] dan menukar a[i] dengan a[j]. Setiap lintasan menetapkan satu posisi, sehingga waktu eksekusinya adalah O(n) dan ruang tambahannya adalah O(1). reset() mengembalikan salinan snapshot; sumber acak dapat diinjeksi untuk reproduktibilitas dan pengujian statistik.”

Pembahasan mendalam langkah demi langkah

Langkah 1: Mengisolasi status. Salin input ke original dan working; reset() menyalin original lagi sehingga referensi eksternal tidak dapat mengubah baseline.

Langkah 2: Tentukan batas acak. Biarkan i berkurang dari n - 1 ke 1. Dengan API setengah terbuka, panggil randomInt(i + 1) untuk mendapatkan 0..i; dengan API inklusif, oper 0 dan i secara eksplisit.

Langkah 3: Swap in-place. Tukar working[i] dan working[j]; posisi i sekarang telah ditetapkan dan tidak ada array sementara berukuran sama yang dibuat.

Langkah 4: Jelaskan keseragaman. Posisi tetap pertama memiliki n pilihan yang berkemungkinan sama, posisi berikutnya memiliki n-1, dan seterusnya, menghasilkan n! jalur pilihan yang berkemungkinan sama. Sumber acak harus seragam di setiap indeks kandidat.

Langkah 5: Tangani duplikat. Algoritma ini seragam atas posisi elemen. Nilai yang berulang dapat membuat beberapa permutasi posisi tampil sebagai urutan nilai yang sama; urutan yang terlihat tidak sama dengan permutasi posisi.

Langkah 6: Implementasikan reset. Kembalikan salinan dari original dan buat ulang working; mengekspos array internal akan memungkinkan pemanggil membuat alias dan merusak baseline.

Langkah 7: Verifikasi dan nyatakan kompleksitas. Gunakan seed tetap untuk reproduktibilitas, hitung frekuensi array kecil untuk keseragaman perkiraan, dan uji array kosong serta array satu elemen. Setiap pengacakan membutuhkan waktu O(n) dan ruang bantu O(1); snapshot yang disimpan itu sendiri menggunakan status O(n).

Jawaban model

“Saya memelihara array original dan working. shuffle mengiterasi i = n-1..1, mengambil j ∈ [0,i] yang seragam, dan menukar kedua entri tersebut; reset mengembalikan salinan dari original dan membangun kembali working. Menukar posisi acak arbitrer secara berulang dapat menulis ulang posisi sebelumnya dan menghasilkan permutasi yang bias. Fisher–Yates hanya mengambil sampel prefiks yang belum ditetapkan, sehingga setiap permutasi posisi memiliki kemungkinan yang sama. Ini berjalan dalam waktu O(n) dan tidak memerlukan array tambahan di luar snapshot status. Saya akan menginjeksi sumber acak untuk pengujian dengan seed dan menggantinya dengan CSPRNG ketika hasilnya memengaruhi keamanan atau keadilan.”

Kesalahan umum

• Mengambil sampel [0,n-1] setiap putaran → posisi yang telah ditetapkan diubah lagi → gunakan [0,i].
• Menghitung floor(random * i) → indeks i tidak pernah dipilih → gunakan i + 1 sebagai batas setengah terbuka.
• Menukar pasangan acak arbitrer sebanyak n kali → permutasi tidak dijamin seragam → tetapkan satu posisi per langkah Fisher–Yates.
• Mengembalikan referensi internal yang sama dari reset → pemanggil dapat merusak baseline → kembalikan salinan defensif.
• Memperlakukan PRNG sebagai keacakan yang aman → hasil undian mungkin dapat diprediksi → pilih CSPRNG untuk model ancaman.

Pertanyaan lanjutan dan tanggapan

Lanjutan 1: Mengapa loop dapat dijalankan ke depan sebagai gantinya?

Bentuk maju menetapkan i dengan mengambil sampel dari [i,n-1]; pembuktiannya simetris. Invariannya adalah bahwa setiap pilihan hanya berasal dari wilayah yang belum ditetapkan.

Lanjutan 2: Bagaimana cara membuktikan keseragaman?

Posisi n-1 memiliki n pilihan yang kemungkinannya sama, posisi n-2 memiliki n-1, dan seterusnya. Oleh karena itu, setiap jalur pilihan lengkap memiliki probabilitas 1/n!.

Lanjutan 3: Bagaimana cara menguji keacakan?

Jalankan banyak percobaan pada array kecil, bandingkan frekuensi permutasi dengan toleransi, dan gunakan seed tetap untuk memverifikasi reproduktibilitas. Sampel terbatas adalah bukti, bukan pembuktian mutlak.

Lanjutan 4: Kapan keacakan semu biasa tidak mencukupi?

Gunakan CSPRNG sistem saat undian, token, atau pengacakan memengaruhi keamanan atau hak akses. PRNG dengan seed cocok untuk simulasi, game, dan pengujian.

Lanjutan 5: Bagaimana jika inputnya adalah linked list?

Mengonversi ke array membutuhkan ruang O(n). Pertukaran node dapat mempertahankan penyimpanan tetapi akses acak menjadi mahal, sehingga kendala harus dinegosiasikan ulang.

Lanjutan 6: Bagaimana cara menangani panggilan konkuren?

Berikan status terisolasi pada setiap instans dan kunci mutasi, atau kembalikan snapshot yang tidak dapat diubah (immutable). Pemanggil tidak boleh mengamati pertukaran parsial saat utas lain melakukan reset.

Lanjutan 7: Apakah pustaka standar Java menggunakan ide ini?

Oracle mendokumentasikan penelusuran mundur yang menukar elemen acak ke posisi saat ini; dengan sumber yang adil, semua permutasi terjadi dengan kemungkinan yang sama.