Temu Duga Pengekodan: Bagaimanakah Anda Melaksanakan Set Jarang (Sparse Set) dengan Operasi O(1)?

Masalah dan skop

Diberikan semesta integer bersempadan [0, U), laksanakan set dengan insert(x), remove(x), contains(x), clear(), dan lelaran ke atas ahli semasa. Empat operasi pertama mestilah O(1) untuk kes terburuk; lelaran mengambil masa O(k) untuk k ahli semasa. Duplikasi ditolak, dan pemadaman nilai yang tiada ialah no-op.

Rekod temu duga awam menyertakan bentuk soalan ini dalam perbincangan Pure Storage. Ujian utamanya ialah invarian tatasusunan dense/sparse, bukan menghafal kelas pustaka.

Perkara yang diuji oleh penemu duga

• Sama ada anda menyatakan bahawa semesta tetap diperlukan; tuntutan O(1) tidak terpakai secara percuma kepada integer sewenang-wenangnya.
• Sama ada anda mengekalkan dense[sparse[x]] == x dan menggunakannya untuk menghalang positif palsu daripada indeks lapuk (stale index).
• Sama ada pemadaman menukar kedudukan dengan elemen terakhir, memastikan awalan dense kekal berdampingan (berterusan) dan lelaran pada O(k).
• Sama ada anda menyatakan ruang O(U) dan mengenali masa set cincangan (hash set) atau peta bit (bitmap) lebih sesuai.

Penjelasan sebelum mengekod

1. Adakah U diketahui, dan bolehkah penyelesaian memperuntukkan dua tatasusunan dengan panjang U? Ini ialah prasyarat sumber.
2. Adakah iterate() mesti diisih? Reka bentuk ini mengembalikan semua ahli tetapi tidak menjanjikan susunan.
3. Adakah lelaran stabil atau akses serentak (concurrent access) diperlukan? Keperluan tersebut mengubah semantik swap-delete dan penyegerakan.
4. Adakah clear() mesti mengelakkan pengimbasan U? Gesaan memerlukan masa malar, jadi ia hanya menetapkan semula size.

Jawapan 30 saat

“Saya mengekalkan tatasusunan indeks sparse dengan panjang U, tatasusunan dense dengan panjang U, dan size semasa. Elemen x hadir secara tepat apabila sparse[x] < size dan dense[sparse[x]] == x. Insert menulis x pada dense[size] dan merekodkan indeks; remove menulis ganti slotnya dengan elemen terakhir dan membetulkan indeks elemen tersebut; clear hanya menetapkan size kepada sifar. Empat operasi teras ialah O(1) kes terburuk, lelaran ke atas awalan dense ialah O(k), dan ruang ialah O(U).”

Pecahan langkah demi langkah secara mendalam

Langkah 1: Nyatakan invarian.

dense[0..size) mengandungi setiap ahli tepat sekali. Bagi ahli x, sparse[x] ialah kedudukannya dalam dense dan dense[sparse[x]] == x. Bukan ahli mungkin mengekalkan nilai sparse yang lama, jadi contains tidak boleh hanya menyemak sama ada indeks berada dalam julat.

Langkah 2: Carian dan pemasukan.

contains(x) menyemak 0 <= x < U, kemudian mengesahkan sparse[x] < size dan pautan baliknya (reverse link). Insert memanggil contains terlebih dahulu; jika tiada, ia menulis x ke dense[size], menetapkan sparse[x] = size, dan menambah size.

Langkah 3: Swap-delete.

Jika x berada pada kedudukan i, biarkan last = dense[size - 1]. Tulis last ke dense[i], kemas kini sparse[last] = i, dan kurangkan size. Tidak perlu mengosongkan sparse[x]: selepas saiz berubah, semakan pautan balik menjadikan entri lapuk tidak sah. Memadam elemen terakhir mengikut logik yang sama.

Langkah 4: Clear masa malar dan lelaran linear.

clear() menetapkan size = 0; kandungan tatasusunan lama tidak lagi dibaca sebagai ahli. Lelaran hanya mengimbas dense[0] hingga dense[size - 1], jadi kosnya ialah O(k), bukan O(U).

Langkah 5: Kerumitan dan sempadan.

contains, insert, remove, dan clear ialah O(1) untuk kes terburuk; lelaran ialah O(k); ruang ialah O(U). Dokumen GCC menyatakan perwakilan ini berguna untuk semesta tetap dan pengenalan mesra cache. Jika semesta tidak diketahui, mesti berkembang, atau terlalu besar untuk memori, set cincangan atau peta bit mungkin lebih sesuai.

Langkah 6: Uji invarian.

Bandingkan setiap operasi rawak dengan rujukan Set. Liputi set kosong, pemasukan duplikasi, memadam nilai yang tiada, memadam elemen tengah dan terakhir, penggunaan semula selepas clear, serta nilai 0 dan U-1. Selepas setiap operasi, sahkan bahawa awalan dense tidak mempunyai duplikasi dan pautan balik setiap ahli adalah sah.

Contoh jawapan berkualiti tinggi

“Semesta bersempadan [0, U) membolehkan saya menukar dua tatasusunan untuk operasi masa malar berketetapan (deterministik). Dense menyimpan awalan padat bagi ahli semasa, manakala sparse memetakan nilai kembali ke indeks dense-nya. Keahlian mesti menyemak sempadan, indeks < size, dan pautan balik; menyemak nombor sparse sahaja tidak selamat. Remove menukar masuk elemen terakhir dan mengemas kini indeks sparse-nya, manakala clear hanya menetapkan semula saiz. Kemas kini dan carian ialah O(1) kes terburuk, lelaran ialah O(k), dan ruang ialah O(U). Jika semesta tidak dikawal, saya akan memilih set cincangan atau peta bit sebaliknya.”

Kesilapan lazim

• Hanya menyemak sparse[x] < size → nilai yang tiada boleh mengekalkan indeks yang kelihatan munasabah → semak juga dense[sparse[x]] == x.
• Menginjak (shifting) semua elemen kemudian semasa pemadaman → pemadaman menjadi O(U) atau O(k) → tukar kedudukan dengan elemen terakhir.
• Mengisi tatasusunan semasa clear → clear menjadi O(U) → tetapkan semula saiz sahaja.
• Mengabaikan semesta bersempadan → akses luar batas atau memori yang tidak boleh diterima → sahkan [0, U) dan kapasiti terlebih dahulu.
• Memanggil lelaran sebagai O(1) → mendapatkan paparan (view) ialah masa malar, tetapi menggunakan semua ahli ialah O(k) → pisahkan kedua-dua kos tersebut.

Soalan susulan dan jawapan

Susulan 1: Bagaimanakah anda menyokong integer sewenang-wenangnya?

Mampatkan koordinat nilai ke dalam [0, U) terlebih dahulu. Jika domain nilai terus berkembang atau tidak boleh diimbas terlebih dahulu, set cincangan adalah lebih wajar, tetapi tuntutan masa malarnya adalah secara terlunas (amortized) atau jangkaan dan bukannya jaminan kes terburuk dalam gesaan ini.

Susulan 2: Bagaimanakah anda mengekalkan susunan lelaran?

Swap-delete menukar susunan dense. Mengekalkan susunan pemasukan memerlukan senarai terpaut tambahan atau tatasusunan stabil, yang mengubah kos pemadaman dan ruang. Sahkan sama ada susunan adalah sebahagian daripada kontrak antara muka sebelum menambahnya.

Susulan 3: Bilakah anda memilih peta bit (bitmap)?

Pilih peta bit apabila keahlian adalah satu-satunya operasi, semestanya sederhana, dan satu bit bagi setiap nilai adalah penting. Pilih sparse set apabila penghitungan pantas juga penting; pilihan yang tepat bergantung pada U, kekardinalan dan corak akses.