Prompt dan konteks yang berlaku
Set harus dapat menguji keanggotaan, menyisipkan, menghapus, dan mengembalikan elemen saat ini secara acak seragam. Hash map menyediakan pencarian cepat sementara dynamic array menyediakan pengindeksan acak; menghapus elemen di tengah adalah tantangannya.
Apa yang dinilai oleh pewawancara
- Menggabungkan hash map dan array alih-alih memaksakan satu struktur untuk melakukan segalanya.
- Memelihara pemetaan nilai-ke-indeks-array dan memperbaruinya setelah setiap pertukaran (swap).
- Memahami rata-rata O(1) dan pertumbuhan array teramortisasi.
- Mendefinisikan semantik getRandom seragam dan nilai duplikat.
- Menangani set kosong, penghapusan elemen yang tidak ada, dan batasan konkurensi.
Pertanyaan klarifikasi sebelum menjawab
- Apakah nilainya unik? Duplikat memerlukan pemetaan suatu nilai ke kumpulan (set) indeks.
- Apakah getRandom harus seragam (uniform), atau boleh mengembalikan anggota acak mana saja? Uji penerimaan akan berbeda.
- Apakah O(1) merupakan rata-rata teramortisasi atau kasus terburuk yang ketat? Kebijakan tabrakan hash (hash collision) mengubah jaminan tersebut.
- Apakah API mengembalikan nilai atau handle? Objek yang dapat berubah (mutable) memerlukan aturan kesetaraan dan hashing.
- Apakah thread safety, memori tetap, atau keacakan yang dapat direproduksi diperlukan?
Kerangka jawaban 30 detik
“Saya menyimpan array items dan hash map indexOf. Insert menambahkan nilai baru di akhir dan mencatat indeksnya; getRandom mengambil sampel indeks array yang seragam. Remove mencari indeks target, memindahkan elemen terakhir ke slot tersebut, memperbarui indeks elemen yang dipindahkan, melakukan pop pada array, dan menghapus pemetaan target. Hal ini menghindari pergeseran O(n). Operasi hash dan pertumbuhan dynamic-array rata-rata bernilai O(1) teramortisasi; set kosong mengembalikan kesalahan yang telah disepakati, dan nilai duplikat memerlukan pemetaan set indeks.”
Pembahasan mendalam langkah demi langkah
Langkah 1: Menetapkan invarian. Untuk setiap nilai v, indexOf[v] menunjuk ke lokasi uniknya di items; array tidak memiliki celah kosong dan setiap indeks berada dalam rentang yang valid.
Langkah 2: Mengimplementasikan insert. Jika map sudah berisi nilai tersebut, kembalikan false sesuai ketentuan. Jika tidak, tambahkan di akhir dan simpan indeks baru dalam rata-rata O(1).
Langkah 3: Mengimplementasikan remove. Baca indeks target i dan indeks terakhir last. Jika i !== last, tulis nilai terakhir ke items[i] dan ubah entri map-nya menjadi i; kemudian lakukan pop pada slot terakhir dan hapus entri target.
Langkah 4: Mengimplementasikan getRandom. Ambil sampel indeks seragam dari array yang tidak kosong. Dokumentasi choice di Python mendefinisikan pemilihan urutan dengan probabilitas yang sama; urutan iterasi hash bukan merupakan jaminan keacakan.
Langkah 5: Menyatakan kompleksitas. Pencarian hash, penambahan di akhir (append), penukaran (swap), dan pop rata-rata bernilai O(1) teramortisasi; ruang array dan map adalah O(n). Tabrakan hash kasus terburuk atau jeda akibat perubahan ukuran (resize) memerlukan diskusi SLO terpisah.
Langkah 6: Menangani duplikat. Ubah indexOf[v] menjadi sebuah set indeks. Saat menghapus satu instans, hapus indeksnya dan terapkan tail-swap yang sama sambil memperbarui kedua set indeks.
Langkah 7: Memverifikasi batasan (boundaries). Uji set kosong, satu item, penghapusan berulang, menghapus elemen terakhir, pertumbuhan berulang, dan seed tetap. Jalankan banyak panggilan getRandom untuk memeriksa frekuensi, bukan hanya keanggotaan.
Contoh jawaban model
“Saya menyimpan nilai-nilai saat ini dalam sebuah array dan indeks array dari setiap nilai dalam sebuah hash map. Untuk menghapus item di tengah, saya memindahkan item terakhir ke slotnya, memperbarui indeks item tersebut, dan melakukan pop pada item terakhir, sehingga tidak ada elemen yang bergeser. getRandom membaca indeks array yang dipilih secara seragam, membuat setiap nilai unik memiliki peluang yang sama. Klaim O(1) adalah rata-rata teramortisasi untuk operasi hash dan pertumbuhan dynamic-array; jika duplikat diizinkan, saya mengganti indeks tunggal dengan set indeks dan mendefinisikan penghapusan sebagai penghapusan satu instans.”
Kesalahan umum
- Hanya menggunakan hash map → getRandom memindai setiap kunci → tambahkan array yang ringkas.
- Menggeser elemen setelah penghapusan → delete menjadi O(n) → tukar dengan elemen terakhir (tail).
- Melupakan indeks nilai yang dipindahkan → penghapusan berikutnya menargetkan slot yang salah → perlakukan pembaruan map sebagai bagian dari penukaran.
- Mengambil sampel dari iterator hash → urutan iterasi tidak menjamin keseragaman → ambil sampel indeks array.
- Menyebut rata-rata O(1) sebagai O(1) kasus terburuk → tabrakan dan biaya resize diabaikan → nyatakan asumsi amortisasi.
Pertanyaan lanjutan dan tanggapan
Pertanyaan lanjutan 1: Apa yang terjadi saat menghapus elemen array terakhir?
Indeks target sama dengan indeks terakhir, jadi cukup lakukan pop dan hapus entri map-nya tanpa perlu melakukan penukaran.
Pertanyaan lanjutan 2: Bagaimana cara mendukung nilai duplikat?
Petakan setiap nilai ke sebuah set indeks. Setelah memindahkan elemen terakhir, hapus indeks lamanya, tambahkan indeks baru, dan hapus satu indeks dari set target.
Pertanyaan lanjutan 3: Bagaimana cara membuktikan bahwa getRandom seragam?
Setiap instans saat ini menempati satu posisi array, dan indeksnya seragam di atas 0..n-1; oleh karena itu, nilai-nilai unik masing-masing menempati satu posisi dengan peluang yang sama.
Pertanyaan lanjutan 4: Bisakah tabrakan hash merusak O(1)?
Kompleksitas rata-rata bergantung pada load factor dan kualitas hash. Jaminan kasus terburuk yang ketat memerlukan bucket berbentuk pohon (treeified buckets), randomized hashing, atau struktur lain.
Pertanyaan lanjutan 5: Bagaimana cara menangani pembacaan dan penghapusan secara bersamaan (concurrent)?
Lindungi pembacaan indeks acak dan penukaran pada operasi penghapusan dengan satu kunci (lock) atau pemeriksaan versi; jika tidak, pembaca dapat mengamati indeks yang telah di-pop.
Pertanyaan lanjutan 6: Bagaimana cara menguji distribusinya?
Jalankan banyak pengujian pada set tetap, hitung setiap nilai, tetapkan toleransi statistik, dan pastikan juga bahwa setiap nilai yang dikembalikan tetap ada di dalam set.