Temu Duga Pengekodan: Bagaimanakah Anda Melaksanakan Set Selang dengan Penggabungan dan Pertanyaan?

Kehendak soalan dan skop

Laksanakan set selang dengan add([l,r)), remove([l,r)), contains(x), dan overlaps([l,r)). Selang yang bersebelahan atau bertindih hendaklah digabungkan secara automatik, manakala pembuangan boleh membelah selang. Terangkan sempadan terbuka dan tertutup, julat kosong, serta kekompleksan.

Ini menguji koleksi teratur, invarian, dan pengendalian sempadan. Dokumentasi bisect Python menyatakan bahawa pembahagian dua mencari titik penyisipan manakala penyisipan senarai masih boleh menjadi O(n). Nyatakan andaian saiz data dan sama ada pepohon diperlukan dan bukannya mendakwa setiap operasi adalah O(log n).

Perkara yang sedang diuji oleh penemu duga

Pertama, bolehkah anda menetapkan semantik separuh terbuka dan mengendalikan selang bersebelahan? Kedua, adakah penyisipan dan pembuangan hanya mengimbas jiran yang berpotensi bersilang dan bukannya setiap selang? Ketiga, bolehkah anda memilih tatasusunan, pepohon seimbang, atau pepohon selang berdasarkan skala dan membuktikan invarian tersebut?

Soalan untuk dijelaskan sebelum menjawab

Adakah selang tertutup, terbuka, atau separuh terbuka? Andaikan [l,r), supaya [0,1) dan [1,2) tidak bersilang.
Adakah titik hujung merupakan titik terapung? Andaikan integer yang boleh dibandingkan; tentukan ketepatan dan peraturan NaN jika sebaliknya.
Patutkah selang bersebelahan digabungkan? Andaikan ya, untuk mengekalkan perwakilan yang dinormalkan.
Apakah skala dan nisbah baca/tulis? Set kecil boleh menggunakan tatasusunan terisih; set besar mungkin memerlukan pepohon seimbang atau pepohon selang.
Apakah kesan membuang julat yang tidak wujud? Andaikan ia idempoten dan kekalkan hanya bahagian yang wujud.

Kerangka jawapan 30 saat

"Saya akan menggunakan selang separuh terbuka dan memastikannya terisih, tak bersilang, dan tidak bersebelahan. add menggunakan carian binari untuk mencari kemungkinan persilangan pertama, kemudian mengimbas ke kanan untuk menggabungkan entri yang bertindih atau bersebelahan. remove mengimbas persilangan dan mengekalkan baki kiri dan kanan yang tidak kosong. contains menyemak selang pendahulu; overlaps menyemak selang pertama yang penghujungnya melebihi permulaan pertanyaan. Tatasusunan mempunyai carian O(log n) tetapi anjakan O(n); untuk set yang lebih besar saya akan menggunakan pepohon seimbang atau pepohon selang."

Analisis mendalam langkah demi langkah

Langkah 1: Tentukan invarian yang dinormalkan

Simpan selang separuh terbuka yang terisih, tak bersilang, dan tidak bersebelahan [l,r) dengan l < r; selang kosong tidak sekali-kali dimasukkan. Selepas dinormalkan, sesuatu titik berada dalam paling banyak satu selang, jadi kemas kini boleh memfokuskan kepada jiran tempatan.

Langkah 2: Pilih storan

Bagi beberapa ribu selang dan operasi penulisan yang rendah, tatasusunan terisih adalah mudah dan boleh dipercayai; carian binari mencari kedudukan manakala penyisipan dan pemadaman menginjakkan elemen. Bagi volum penulisan dan pertanyaan yang tinggi, gunakan pepohon seimbang dengan kunci teratur. Tambah pepohon selang tertambah (augmented interval tree) hanya apabila kiraan liputan atau kedalaman pertindihan maksimum diperlukan.

Langkah 3: Cari jiran penyisipan

Gunakan bisect_left untuk mencari permulaan pertama yang tidak kurang daripada l, kemudian periksa satu pendahulu kerana ia mungkin melangkaui l. Imbas ke kanan selagi permulaan seterusnya adalah paling banyak bersamaan penghujung cantuman semasa; selang bersebelahan disertakan dalam penggabungan.

text

add(l, r):
    i = first index with start >= l, then i = max(0, i - 1)
    while i < len(intervals) and intervals[i].end >= l:
        l = min(l, intervals[i].start)
        r = max(r, intervals[i].end)
        delete intervals[i]
    insert [l, r) at i

Langkah 4: Laksanakan pembuangan dan pembelahan

Cari selang pertama yang mungkin bersilang dengan [l,r) dan proses sehingga permulaan seterusnya sekurang-kurangnya r. Bagi setiap selang, kekalkan bahagian bukan kosong [start,l) dan [r,end). Oleh sebab input telah dinormalkan, pembuangan tidak menghasilkan julat bersebelahan yang memerlukan penggabungan semula.

Langkah 5: Laksanakan pertanyaan titik dan julat

Bagi contains(x), cari selang terakhir dengan start <= x dan semak x < end. Bagi overlaps([l,r)), cari selang pertama dengan end > l; ia bertindih jika start < r. Julat pertanyaan yang kosong mengembalikan false. Setiap perbandingan mengikut semantik separuh terbuka.

Langkah 6: Buktikan ketepatan

Gelung penyisipan hanya membuang julat yang bertindih atau menyentuh julat baharu dan menggantikan kesatuannya dengan satu selang, jadi liputan terpelihara. Pembuangan hanya memadamkan persilangan dan mengekalkan dua perbezaan tersebut. Susunan terisih dan sifat tidak bersebelahan dipulihkan selepas setiap operasi, dan setiap pertanyaan hanya memerlukan satu calon pendahulu atau pengganti.

Langkah 7: Analisis kekompleksan

Pencarian lokasi tatasusunan adalah O(log n), tetapi penginjakan dan pemadaman entri yang digabungkan boleh menjadi O(n), dengan n ialah bilangan selang. Mengimbas k selang jiran menambah O(k). Pepohon seimbang boleh menyediakan kemas kini tempatan O(log n + k) dengan kos pelaksanaan dan memori yang lebih tinggi. Jangan kelirukan kos carian binari dengan kos operasi lengkap.

Langkah 8: Reka bentuk ujian sempadan

Uji set kosong, julat kosong, cantuman bersebelahan, pembendungan penuh, pertindihan separa, merangkumi beberapa selang, pemadaman tengah, pemadaman titik hujung, nombor negatif, operasi berulang, dan julat pertanyaan yang besar. Lakukan ujian pembezaan operasi rawak terhadap model tatasusunan boolean mengikut titik (pointwise).

Pertukaran dan batasan

Pertukaran 1: Selang separuh terbuka atau tertutup

Julat separuh terbuka bergabung secara semula jadi, mempunyai panjang r-l, dan sesuai untuk kes penggunaan masa dan indeks tatasusunan. Logik perniagaan selang tertutup mesti mengubah peraturan selang bersebelahan, panjang, dan limpahan integer secara konsisten; menukar operator perbandingan sahaja adalah tidak selamat.

Pertukaran 2: Tatasusunan atau pepohon seimbang

Tatasusunan adalah ringkas dan mesra cache untuk set kecil hingga sederhana yang banyak membaca. Pepohon mengendalikan banyak penyisipan dan pemadaman tetapi memerlukan kunci teratur dan peraturan pembatalan lelaran (iterator invalidation). Buat pilihan berdasarkan nilai n sebenar, nisbah penulisan, dan bajet kependaman.

Pertukaran 3: Gabungkan julat bersebelahan atau kekalkan asal-usul (provenance)

Penggabungan mengurangkan entri dan memudahkan pertanyaan. Jika selang mewakili kebenaran, tempahan, atau tempoh perakaunan yang sempadan asalnya penting, kekalkan metadata sumber atau gunakan perwakilan yang tidak membuang segmen.

Latihan kegagalan dan pelan evolusi

Latihan 1: Banyak sisipan bersebelahan

Sisipkan 10,000 selang bersebelahan dalam susunan terbalik. Sahkan bahawa satu selang yang dinormalkan kekal tanpa sebarang titik hujung yang hilang, kemudian ukur anjakan tatasusunan untuk memutuskan sama ada pepohon diperlukan.

Latihan 2: Penyisipan dan pembuangan rawak

Jana operasi add, remove, contains, dan overlaps secara rawak dan bandingkan dengan model pointwise. Periksa terutamanya bahawa pemadaman bahagian tengah satu selang dan penyisipan kemudian menggabungkan kedua-dua belah pihak dengan betul.

Latihan 3: Sempadan dan input tidak sah

Uji l == r, l > r, integer yang sangat besar, dan NaN. Tentukan sama ada julat kosong mengembalikan hasil serta-merta, julat terbalik menghasilkan ralat atau ditukar, dan input titik terapung ditolak.

Kesilapan lazim dan tindakan susulan

Kesilapan 1: Mengelirukan bersebelahan dan bertindih

Selang separuh terbuka [0,1) dan [1,2) tidak bersilang, walaupun set yang dinormalkan mungkin masih menggabungkannya. Tentukan syarat persilangan dan cantuman secara berasingan.

Kesilapan 2: Menyemak jiran sebelah kanan sahaja

Pendahulu boleh melangkaui titik hujung kiri baharu. Periksa satu pendahulu selepas carian binari.

Kesilapan 3: Meninggalkan selang kosong selepas pembuangan

Tapis setiap perbezaan dengan start >= end, jika tidak contains boleh melaporkan padanan palsu (phantom hit).

Kesilapan 4: Mendakwa bisect menjadikan penyisipan O(log n)

Python secara jelas menyatakan bahawa anjakan penyisipan senarai adalah O(n). Nyatakan kos carian, anjakan, dan imbasan secara berasingan.

Kesilapan 5: Mengabaikan sempadan titik terapung

NaN tidak mengikut susunan biasa, dan kesamarataan anggaran menjadikan sifat bersebelahan tidak stabil. Tentukan penormalan ketepatan sebelum membenarkan apungan.

Kesilapan 6: Mengabaikan asal-usul (provenance)

Jika selang mewakili kebenaran, tempahan, atau tempoh perakaunan, kesatuan boleh menghilangkan maksud sumber asalnya. Simpan metadata atau jangan gabungkan segmen tersebut.