Wawancara Koding: Bagaimana Cara Mengimplementasikan Sparse Set dengan Operasi O(1)?

Masalah dan cakupan

Diberikan sebuah semesta bilangan bulat terbatas [0, U), implementasikan set dengan insert(x), remove(x), contains(x), clear(), dan iterasi pada elemen-elemen saat ini. Empat operasi pertama harus memiliki kasus terburuk O(1); iterasi membutuhkan waktu O(k) untuk k elemen saat ini. Duplikat ditolak, dan menghapus nilai yang tidak ada adalah operasi tanpa aksi (no-op).

Catatan wawancara publik mencakup bentuk pertanyaan ini dalam diskusi Pure Storage. Ujian utamanya adalah invarian larik dense/sparse, bukan menghafal kelas pustaka.

Hal yang diuji oleh pewawancara

• Apakah Anda menyatakan bahwa semesta tetap diperlukan; klaim O(1) tidak berlaku untuk bilangan bulat arbitrer begitu saja.
• Apakah Anda mempertahankan dense[sparse[x]] == x dan menggunakannya untuk mencegah positif palsu akibat indeks basi (stale index).
• Apakah penghapusan menukar elemen dengan elemen terakhir, menjaga prefiks dense tetap bersebelahan (kontigu) dan iterasi pada O(k).
• Apakah Anda menyatakan ruang O(U) dan mengenali kapan hash set atau bitmap lebih sesuai.

Klarifikasi sebelum menulis kode

1. Apakah U diketahui, dan bisakah solusi mengalokasikan dua larik dengan panjang U? Ini adalah prasyarat sumber daya.
2. Apakah iterate() harus terurut? Desain ini mengembalikan semua elemen tetapi tidak menjanjikan urutan.
3. Apakah iterator yang stabil atau akses serentak (concurrent access) diperlukan? Persyaratan tersebut mengubah semantik swap-delete dan sinkronisasi.
4. Apakah clear() harus menghindari pemindaian U? Soal membutuhkan waktu konstan, sehingga ia hanya mereset size.

Jawaban 30 detik

“Saya menyimpan larik indeks sparse dengan panjang U, larik dense dengan panjang U, dan size saat ini. Suatu elemen x ada jika dan hanya jika sparse[x] < size dan dense[sparse[x]] == x. Insert menulis x pada dense[size] dan mencatat indeksnya; remove menimpa slotnya dengan elemen terakhir dan memperbaiki indeks elemen tersebut; clear hanya menyetel size ke nol. Empat operasi inti memiliki kasus terburuk O(1), iterasi pada prefiks dense adalah O(k), dan ruang adalah O(U).”

Pembahasan mendalam langkah demi langkah

Langkah 1: Nyatakan invarian.

dense[0..size) berisi setiap elemen tepat satu kali. Untuk sebuah elemen x, sparse[x] adalah posisinya di dense dan dense[sparse[x]] == x. Elemen non-anggota dapat mempertahankan nilai sparse lama, sehingga contains tidak bisa hanya memeriksa apakah indeks berada dalam rentang.

Langkah 2: Pencarian dan penyisipan.

contains(x) memeriksa 0 <= x < U, lalu memvalidasi sparse[x] < size dan tautan balik (reverse link). Insert memanggil contains terlebih dahulu; jika tidak ada, ia menulis x ke dense[size], menetapkan sparse[x] = size, dan menambah size.

Langkah 3: Swap-delete.

Jika x berada pada posisi i, misalkan last = dense[size - 1]. Tulis last ke dense[i], perbarui sparse[last] = i, dan kurangi size. Tidak perlu membersihkan sparse[x]: setelah ukuran berubah, pemeriksaan tautan balik membuat entri basi menjadi tidak valid. Menghapus elemen terakhir mengikuti logika yang sama.

Langkah 4: Clear waktu konstan dan iterasi linear.

clear() menyetel size = 0; konten larik lama tidak lagi dibaca sebagai elemen. Iterasi hanya memindai dense[0] hingga dense[size - 1], sehingga biayanya adalah O(k), bukan O(U).

Langkah 5: Kompleksitas dan batasan.

contains, insert, remove, dan clear adalah O(1) kasus terburuk; iterasi adalah O(k); ruang adalah O(U). Dokumen GCC mencatat representasi ini berguna untuk semesta tetap dan enumerasi yang ramah cache. Jika semesta tidak diketahui, harus membesar, atau terlalu besar untuk memori, hash set atau bitmap mungkin lebih cocok.

Langkah 6: Uji invarian.

Bandingkan setiap operasi acak dengan referensi Set. Cakup himpunan kosong, penyisipan duplikat, penghapusan nilai yang tidak ada, penghapusan elemen tengah dan terakhir, penggunaan kembali setelah clear, serta nilai 0 dan U-1. Setelah setiap operasi, verifikasi bahwa prefiks dense tidak memiliki duplikat dan tautan balik setiap elemen valid.

Contoh jawaban berkualitas tinggi

“Semesta terbatas [0, U) memungkinkan saya menukar dua larik untuk operasi deterministik berwaktu konstan. Dense menyimpan prefiks kompak dari elemen saat ini, sedangkan sparse memetakan nilai kembali ke indeks dense-nya. Keanggotaan harus memeriksa batas, indeks < size, dan tautan balik; memeriksa angka sparse saja tidak aman. Remove menukar elemen terakhir dan memperbarui indeks sparse-nya, sedangkan clear hanya mereset ukuran. Pembaruan dan pencarian memiliki kasus terburuk O(1), iterasi adalah O(k), dan ruang adalah O(U). Jika semesta tidak terkontrol, saya akan memilih hash set atau bitmap sebagai gantinya.”

Kesalahan umum

• Hanya memeriksa sparse[x] < size → nilai yang tidak ada dapat menyimpan indeks yang tampak valid → periksa juga dense[sparse[x]] == x.
• Menggeser semua elemen berikutnya saat penghapusan → penghapusan menjadi O(U) atau O(k) → tukar dengan elemen terakhir.
• Mengisi larik selama clear → clear menjadi O(U) → reset ukuran saja.
• Mengabaikan semesta terbatas → akses di luar batas atau penggunaan memori yang tidak dapat diterima → konfirmasikan [0, U) dan kapasitas terlebih dahulu.
• Menyebut iterasi sebagai O(1) → mendapatkan view adalah waktu konstan, tetapi mengonsumsi semua elemen adalah O(k) → pisahkan kedua biaya tersebut.

Pertanyaan lanjutan dan jawaban

Lanjutan 1: Bagaimana Anda mendukung bilangan bulat arbitrer?

Lakukan kompresi koordinat (coordinate-compress) nilai-nilai ke dalam [0, U) terlebih dahulu. Jika domain nilai terus bertambah atau tidak dapat dipindai sejak awal, hash set lebih alami, tetapi klaim waktu konstannya bersifat diamortisasi atau ekspektasi, bukan jaminan kasus terburuk seperti pada soal ini.

Lanjutan 2: Bagaimana Anda mempertahankan urutan iterasi?

Swap-delete mengubah urutan pada dense. Mempertahankan urutan penyisipan memerlukan linked list tambahan atau larik stabil, yang akan mengubah biaya penghapusan dan ruang. Konfirmasikan apakah urutan merupakan bagian dari kontrak antarmuka sebelum menambahkannya.

Lanjutan 3: Kapan Anda memilih bitmap?

Pilih bitmap jika keanggotaan adalah satu-satunya operasi, semestanya moderat, dan efisiensi satu bit per nilai penting. Pilih sparse set jika enumerasi cepat juga penting; pilihan yang tepat bergantung pada U, kardinalitas, dan pola akses.