Gesaan dan konteks berkaitan
Set ini mesti menguji keahlian, menyisip, memadam, dan mengembalikan elemen semasa secara rawak seragam. Peta cincangan menyediakan carian pantas manakala tatasusunan dinamik menyediakan pengindeksan rawak; memadam elemen di bahagian tengah merupakan konflik utamanya.
Perkara yang dinilai oleh penemu duga
- Menggabungkan peta cincangan dan tatasusunan dan bukannya memaksa satu struktur melakukan segala-galanya.
- Mengekalkan pemetaan nilai-ke-indeks-tatasusunan dan mengemas kininya selepas setiap pertukaran (swap).
- Memahami purata O(1) dan pertumbuhan tatasusunan terpelunas (amortized).
- Menentukan semantik getRandom seragam dan nilai pendua.
- Mengendalikan set kosong, pemadaman elemen yang tiada, dan sempadan keserentakan.
Soalan penjelasan sebelum menjawab
- Adakah nilai adalah unik? Nilai pendua memerlukan pemetaan nilai kepada satu set indeks.
- Adakah getRandom mesti seragam, atau bolehkah ia mengembalikan mana-mana ahli rawak? Ujian penerimaan akan berbeza.
- Adakah O(1) merupakan purata terpelunas atau kes terburuk yang ketat? Dasar perlanggaran cincangan (hash collision) mengubah jaminan tersebut.
- Adakah API mengembalikan nilai atau pemegang (handle)? Objek boleh ubah memerlukan peraturan kesaksamaan dan pencincangan.
- Adakah keselamatan benang (thread safety), memori tetap, atau kerawakan yang boleh dihasilkan semula diperlukan?
Rangka jawapan 30 saat
“Saya mengekalkan tatasusunan items dan peta cincangan indexOf. Insert menambah nilai baharu di hujung dan merekodkan indeksnya; getRandom mengambil sampel indeks tatasusunan yang seragam. Remove mencari indeks sasaran, memindahkan elemen terakhir ke dalam slot tersebut, mengemas kini indeks elemen yang dipindahkan, mengeluarkan (pop) elemen tatasusunan, dan memadamkan pemetaan sasaran. Ini mengelakkan anjakan O(n). Operasi cincangan dan pertumbuhan tatasusunan dinamik adalah purata terpelunas O(1); set kosong mengembalikan ralat yang dipersetujui, dan nilai pendua memerlukan pemetaan set indeks.”
Perbincangan mendalam langkah demi langkah
Langkah 1: Wujudkan invarian. Untuk setiap nilai v, indexOf[v] menunjuk ke lokasi uniknya dalam items; tatasusunan tidak mempunyai ruang kosong dan setiap indeks berada dalam julat yang sah.
Langkah 2: Laksanakan insert. Jika peta sudah mengandungi nilai tersebut, kembalikan false seperti yang ditentukan. Jika tidak, tambahkan di hujung dan simpan indeks baharu dalam purata O(1).
Langkah 3: Laksanakan remove. Baca indeks sasaran i dan indeks terakhir last. Jika i !== last, tulis nilai terakhir ke items[i] dan tukar entri petanya kepada i; kemudian lakukan pop pada slot terakhir dan padam entri sasaran.
Langkah 4: Laksanakan getRandom. Ambil sampel indeks seragam daripada tatasusunan yang tidak kosong. Dokumentasi choice Python mentakrifkan pemilihan jujukan berkebarangkalian sama; susunan lelaran cincangan bukan jaminan kerawakan.
Langkah 5: Nyatakan kerumitan. Carian cincangan, penambahan di hujung, pertukaran, dan pop adalah purata terpelunas O(1); ruang tatasusunan dan peta adalah O(n). Perlanggaran cincangan kes terburuk atau jeda saiz semula memerlukan perbincangan SLO yang berasingan.
Langkah 6: Kendalikan nilai pendua. Tukar indexOf[v] kepada satu set indeks. Apabila memadam satu kejadian, buang indeksnya dan gunakan swap hujung yang sama sambil mengemas kini kedua-dua set indeks.
Langkah 7: Sahkan sempadan. Uji set kosong, satu item, pemadaman berulang, memadam elemen hujung, pertumbuhan berulang, dan benih (seed) tetap. Jalankan banyak panggilan getRandom untuk memeriksa kekerapan, bukan sekadar keahlian.
Contoh jawapan model
“Saya menyimpan nilai semasa dalam tatasusunan dan indeks tatasusunan setiap nilai dalam peta cincangan. Untuk memadam item di tengah, saya memindahkan item hujung ke dalam slotnya, mengemas kini indeks item tersebut, dan mengeluarkan item hujung, supaya tiada elemen yang berganjak. getRandom membaca indeks tatasusunan yang dipilih secara seragam, menjadikan setiap nilai unik mempunyai kebarangkalian yang sama. Tuntutan O(1) ialah purata terpelunas bagi operasi cincangan dan pertumbuhan tatasusunan dinamik; jika nilai pendua dibenarkan, saya menggantikan indeks tunggal dengan set indeks dan mentakrifkan pemadaman sebagai penyingkiran satu kejadian.”
Kesilapan lazim
- Hanya menggunakan peta cincangan → getRandom mengimbas setiap kunci → tambah tatasusunan padat.
- Menginjak elemen selepas pemadaman → delete menjadi O(n) → tukar dengan elemen hujung (tail).
- Terlupa indeks bagi nilai yang dipindahkan → pemadaman kemudian menyasarkan slot yang salah → anggap kemas kini peta sebagai sebahagian daripada pertukaran.
- Mengambil sampel daripada lelaran cincangan → susunan lelaran tidak menjamin keseragaman → ambil sampel indeks tatasusunan.
- Memanggil purata O(1) sebagai O(1) kes terburuk → perlanggaran dan kos saiz semula diabaikan → nyatakan andaian terpelunas.
Soalan susulan dan jawapan
Soalan susulan 1: Apakah yang berlaku apabila memadam elemen tatasusunan yang terakhir?
Indeks sasaran adalah sama dengan indeks hujung, jadi lakukan pop dan padamkan entri petanya tanpa perlu melakukan pertukaran.
Soalan susulan 2: Bagaimana anda menyokong nilai pendua?
Petakan setiap nilai kepada satu set indeks. Selepas memindahkan elemen hujung, buang indeks lamanya, tambah indeks baharu, dan buang satu indeks daripada set sasaran.
Soalan susulan 3: Bagaimana anda membuktikan getRandom adalah seragam?
Setiap kejadian semasa menduduki satu kedudukan tatasusunan, dan indeks adalah seragam merentasi 0..n-1; oleh itu nilai-nilai unik masing-masing menduduki satu kedudukan yang berkebarangkalian sama.
Soalan susulan 4: Bolehkah perlanggaran cincangan memecahkan O(1)?
Kerumitan purata bergantung pada faktor beban dan kualiti cincangan. Jaminan kes terburuk yang ketat memerlukan baldi berstruktur pokok (treeified buckets), pencincangan rawak, atau struktur lain.
Soalan susulan 5: Bagaimana anda mengendalikan bacaan dan pemadaman serentak?
Lindungi bacaan indeks rawak dan pertukaran pemadaman dengan satu kunci (lock) atau semakan versi; jika tidak, pembaca boleh memerhatikan indeks yang telah dikeluarkan.
Soalan susulan 6: Bagaimana anda menguji taburan?
Jalankan banyak percubaan pada set tetap, kira setiap nilai, tetapkan toleransi statistik, dan sahkan juga bahawa setiap nilai yang dikembalikan kekal ada dalam set.