Wawancara coding: Mengimplementasikan Range Module yang dapat diubah (mutable)

Petunjuk dan cakupan

Implementasikan tiga operasi pada interval setengah terbuka [left, right): menambahkan cakupan, menguji apakah kueri tercakup sepenuhnya, dan menghapus cakupan. Asumsikan 1 <= left < right <= 10^9 dan hingga 10^4 panggilan, sesuai dengan masalah Range Module publik. Nyatakan apa yang terjadi saat left >= right jika API Anda menerima input defensif.

Hal yang diuji oleh pewawancara

Pengujian utama adalah apakah Anda dapat memilih dan mempertahankan invarian struktur data saat interval disisipkan, dihapus, dan dikueri. Representasi yang diharapkan adalah koleksi kanonikal terurut dari interval-interval yang saling lepas; LeetCode mencantumkan ordered set dan segment tree sebagai pendekatan yang relevan. Magicsheet melabeli masalah ini sulit (hard) dan menandainya dengan ordered set dan segment tree. Pertanyaan ini juga menguji kedisiplinan batas setengah terbuka, keamanan iterator, dan perhitungan kompleksitas.

Pertanyaan klarifikasi yang perlu diajukan

1. Apakah titik akhir bersifat inklusif? Jawaban ini menggunakan [left, right).
2. Apakah rentang yang saling bersentuhan seperti [1,3) dan [3,5) harus digabungkan? Jawaban ini menggabungkannya menjadi satu interval kanonikal.
3. Apakah semua titik akhir diketahui sebelum eksekusi? Desain dasar bersifat online, jadi titik akhir tidak diketahui sebelumnya.
4. Apa yang harus dilakukan terhadap input left >= right yang tidak valid? Kembalikan tanpa mengubah state, atau tolak secara eksplisit.
5. Apakah domain cukup terbatas dan statis untuk membenarkan penggunaan segment tree? Hal tersebut memengaruhi desain alternatif.

Solusi langkah demi langkah

1. Pilih representasi dan invarian

Gunakan ordered map dari awal interval ke akhir interval. std::map menjaga kunci tetap terurut dan mendokumentasikan pencarian, penyisipan, serta penghapusan logaritmik; iterasi menaik memungkinkan algoritma hanya menelusuri interval di sekitarnya. Normalisasikan cakupan yang bersentuhan, sehingga setelah setiap operasi, map tidak berisi pasangan dengan previousEnd >= nextStart.

2. Tambahkan cakupan

Mulai dari interval pertama yang akhirnya setidaknya left (atau interval pertama setelah pendahulu / predecessor). Selama awal saat ini paling banyak sebesar right yang sedang berkembang, perluas left dan right untuk menyertakan interval tersebut, lalu tandai untuk dihapus. Hapus rentang berurutan yang ditandai dan masukkan interval yang telah digabungkan. State kosong dan rentang yang lepas dari kedua tetangganya tidak memerlukan struktur khusus.

3. Hapus cakupan dan kueri cakupan

Untuk penghapusan, kunjungi interval dengan start < right dan end > left. Untuk setiap tumpang tindih, pertahankan [oldStart,left) jika oldStart < left, dan pertahankan [right,oldEnd) jika right < oldEnd; hapus yang asli sebelum menyisipkan fragmen. Untuk kueri, periksa interval yang awalnya merupakan nilai awal terbesar yang tidak melebihi left; kembalikan true hanya jika interval tersebut ada dan akhirnya setidaknya right. Dengan titik akhir setengah terbuka, [1,3) tidak mencakup [3,4).

Kebenaran dan kompleksitas

Invarian membuktikan kebenaran melalui induksi. Penambahan menggantikan setiap interval yang terhubung ke rentang baru dengan gabungannya, sehingga tidak ada titik tercakup yang hilang dan hasilnya bersifat kanonikal. Penghapusan menggantikan setiap tumpang tindih secara tepat dengan bagian di luar rentang yang dihapus. Mengueri pendahulu sudah cukup karena interval saling lepas yang terurut memastikan interval sebelumnya tidak berakhir lebih lambat, dan interval berikutnya yang memiliki awal lebih besar dari left tidak dapat memuat left.

Misalkan n adalah jumlah interval yang disimpan dan k adalah jumlah yang disentuh oleh suatu pembaruan. Kueri bernilai O(log n). Pembaruan melakukan O(log n) pencarian ditambah O(k) penelusuran dan penghapusan iterator; implementasi yang mencari ulang setiap kunci bisa bernilai O(k log n). Kompleksitas ruang adalah O(n). Segment tree masuk akal untuk semesta koordinat terbatas yang diketahui, sedangkan kompresi koordinat memerlukan semua titik akhir secara offline dan tidak cocok untuk panggilan online arbitrer.

Jawaban model

“Saya akan mengimplementasikan ordered map yang dinormalisasi dari interval setengah terbuka, terurut, dan saling lepas. Add mencari dan menggabungkan setiap interval yang tumpang tindih atau bersentuhan, remove menghapus tumpang tindih dan mempertahankan paling banyak dua fragmen batas, dan query memeriksa pendahulu dari awal yang diminta. Kewajiban pembuktian utama adalah bahwa setiap operasi mempertahankan gabungan kanonikal. Query membutuhkan biaya O(log n); pembaruan membutuhkan biaya O(log n + k) saat menghapus rentang iterator yang berurutan dan menggunakan ruang O(n). Saya akan membandingkan online map ini dengan segment tree hanya setelah mengonfirmasi domain koordinat dan apakah semua titik akhir diketahui.”

Kesalahan umum

• Memperlakukan titik akhir sebagai tertutup → rentang yang berdekatan terlihat tumpang tindih secara keliru → tentukan [left,right) terlebih dahulu.
• Membiarkan interval yang bersentuhan tetap terpisah → kueri dan pembaruan berikutnya menemui duplikasi yang seharusnya dapat dihindari → normalisasikan kedekatan.
• Menghapus saat menaikkan iterator yang tidak valid → melewatkan simpul atau mengakses penyimpanan yang telah dibebaskan → simpan iterator berikutnya atau hapus rentang yang diketahui.
• Membagi tanpa mempertahankan kedua sisi → cakupan menghilang pada satu batas → uji penghapusan di tengah dan penahanan penuh.
• Mengklaim setiap pembaruan bernilai O(log n) → satu operasi dapat menyentuh banyak interval → sertakan k dalam batas tersebut.
• Menggunakan kompresi koordinat secara online → titik akhir yang belum terlihat membatalkan indeks → gunakan struktur terurut atau bangun ulang dari himpunan offline yang lengkap.

Tindak lanjut dan ekstensi

Kasus batas mana yang harus diuji?

Uji modul kosong, penambahan berulang, kueri tepat di titik akhir, penambahan yang bersentuhan [1,3) lalu [3,5), penghapusan bagian tengah, penghapusan yang mencakup seluruh interval, penghapusan tanpa tumpang tindih, rentang bersarang, serta titik akhir 0 dan 10^9 jika API mengizinkannya.

Bagaimana Anda menguji invarian tersebut?

Setelah setiap operasi acak, pastikan nilai awal terurut, end > start, dan previousEnd < nextStart. Bandingkan hasil kueri dengan array boolean kecil atau model union brute-force pada domain koordinat yang sangat kecil. Ini akan menangkap bug off-by-one dan kehilangan fragmen.

Kapan segment tree lebih unggul?

Pilih segment tree saat semesta koordinat terbatas atau dapat dikompresi serta agregasi rentang atau lazy propagation diperlukan. Ini memberikan operasi logaritmik yang dapat diprediksi tetapi menambah kompleksitas simpul dan lazy-state; ordered map lebih sederhana untuk interval renggang (sparse) dan online.