Petunjuk dan ruang lingkup
Implementasikan interval set dengan add([l,r)), remove([l,r)), contains(x), dan overlaps([l,r)). Interval yang bersebelahan atau tumpang tindih harus digabungkan secara otomatis, sedangkan penghapusan dapat membagi sebuah interval. Jelaskan batas terbuka dan tertutup, rentang kosong, serta kompleksitas.
Ini menguji koleksi terurut, invarian, dan penanganan batasan. Dokumentasi bisect pada Python menyatakan bahwa biseksi menemukan titik penyisipan sementara penyisipan list masih bisa bernilai O(n). Nyatakan asumsi ukuran data dan apakah struktur tree diperlukan daripada mengklaim bahwa setiap operasi bernilai O(log n).
Hal yang sedang diuji oleh pewawancara
Pertama, bisakah Anda menetapkan semantik setengah terbuka dan menangani ketersebelahan? Kedua, bisakah penyisipan dan penghapusan hanya memindai tetangga yang berpotensi berpotongan alih-alih setiap interval? Ketiga, bisakah Anda memilih array, balanced tree, atau interval tree berdasarkan skala dan membuktikan invarian tersebut?
Pertanyaan untuk diklarifikasi sebelum menjawab
- Apakah interval bersifat tertutup, terbuka, atau setengah terbuka? Asumsikan
[l,r), sehingga[0,1)dan[1,2)tidak berpotongan. - Apakah titik akhir berupa floating point? Asumsikan bilangan bulat yang dapat dibandingkan; tentukan presisi dan aturan NaN jika tidak.
- Haruskah interval yang bersebelahan digabungkan? Asumsikan ya, untuk menjaga representasi yang ternormalisasi.
- Berapa skala dan proporsi baca/tulisnya? Set berukuran kecil dapat menggunakan sorted array; set berukuran besar mungkin memerlukan balanced tree atau interval tree.
- Apa yang terjadi jika menghapus rentang yang tidak ada? Asumsikan idempoten dan pertahankan hanya porsi yang ada.
Kerangka jawaban 30 detik
“Saya akan menggunakan interval setengah terbuka dan menjaganya tetap terurut, saling lepas (disjoint), dan tidak bersebelahan. add menggunakan binary search untuk menemukan kemungkinan perpotongan pertama, lalu memindai ke kanan untuk menggabungkan entri yang tumpang tindih atau bersebelahan. remove memindai perpotongan dan mempertahankan sisa kiri dan kanan yang tidak kosong. contains memeriksa interval pendahulu (predecessor); overlaps memeriksa interval pertama yang titik akhirnya melebihi awal kueri. Array memiliki pencarian O(log n) tetapi pergeseran O(n); untuk set yang lebih besar, saya akan menggunakan balanced tree atau interval tree.”
Pembahasan mendalam langkah demi langkah
Langkah 1: Tentukan invarian yang ternormalisasi
Simpan interval setengah terbuka yang terurut, saling lepas, dan tidak bersebelahan [l,r) dengan l < r; interval kosong tidak pernah dimasukkan. Setelah normalisasi, sebuah titik paling banyak berada dalam satu interval, sehingga pembaruan dapat berfokus pada tetangga lokal.
Langkah 2: Pilih penyimpanan
Untuk beberapa ribu interval dan operasi tulis yang sedikit, sorted array bersifat sederhana dan andal; binary search menemukan posisi sementara penyisipan dan penghapusan menggeser elemen. Untuk volume tulis dan kueri yang tinggi, gunakan balanced tree dengan ordered-key. Tambahkan augmented interval tree hanya jika hitungan cakupan atau kedalaman overlap maksimum diperlukan.
Langkah 3: Temukan tetangga penyisipan
Gunakan bisect_left untuk menemukan titik awal pertama yang tidak lebih kecil dari l, lalu periksa satu pendahulu karena rentangnya mungkin meluas melewati l. Pindai ke kanan selama titik awal berikutnya paling banyak bernilai sebesar akhir penggabungan saat ini; interval yang bersebelahan diikutsertakan dalam penggabungan.
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 iLangkah 4: Implementasikan penghapusan dan pemisahan
Temukan interval pertama yang mungkin berpotongan dengan [l,r) dan proses hingga titik awal berikutnya setidaknya bernilai r. Untuk setiap interval, pertahankan porsi non-kosong dari [start,l) dan [r,end). Karena input sudah ternormalisasi, penghapusan tidak menghasilkan rentang bersebelahan yang memerlukan penggabungan ulang.
Langkah 5: Implementasikan kueri titik dan rentang
Untuk contains(x), temukan interval terakhir dengan start <= x dan periksa x < end. Untuk overlaps([l,r)), temukan interval pertama dengan end > l; interval tersebut tumpang tindih jika start < r. Rentang kueri yang kosong mengembalikan false. Setiap perbandingan mengikuti semantik setengah terbuka.
Langkah 6: Buktikan kebenaran
Loop penyisipan hanya menghapus rentang yang tumpang tindih atau bersentuhan dengan rentang baru dan mengganti gabungannya dengan satu interval, sehingga cakupan tetap terjaga. Penghapusan hanya membuang perpotongan dan mempertahankan dua selisihnya. Keterurutan dan sifat non-bersebelahan dipulihkan setelah setiap operasi, dan setiap kueri hanya membutuhkan satu kandidat pendahulu atau penerus.
Langkah 7: Analisis kompleksitas
Pencarian lokasi pada array bernilai O(log n), tetapi menggeser dan menghapus entri yang digabungkan dapat bernilai O(n), di mana n adalah jumlah interval. Memindai k interval tetangga menambah O(k). Balanced tree dapat menyediakan pembaruan lokal O(log n + k) dengan kompensasi biaya implementasi dan memori yang lebih besar. Jangan menyamakan biaya binary search dengan biaya operasi keseluruhan.
Langkah 8: Rancang pengujian kasus batas
Uji set kosong, rentang kosong, penggabungan bersebelahan, pencakupan penuh, tumpang tindih parsial, mencakup beberapa interval, penghapusan di tengah, penghapusan di titik ujung, nilai negatif, operasi berulang, dan rentang kueri yang besar. Lakukan pengujian diferensial operasi acak terhadap model boolean-array berbasis titik (pointwise).
Kompromi dan batasan
Kompromi 1: Interval setengah terbuka atau tertutup
Rentang setengah terbuka tersusun secara alami, memiliki panjang r-l, dan cocok untuk use case waktu serta indeks array. Kebutuhan bisnis dengan interval tertutup harus secara konsisten mengubah aturan ketersebelahan, panjang, dan overflow integer; hanya mengubah operator perbandingan tidaklah aman.
Kompromi 2: Array atau balanced tree
Array berukuran ringkas dan ramah terhadap cache untuk set data kecil hingga menengah yang dominan operasi baca. Tree menangani banyak penyisipan dan penghapusan dengan baik, tetapi memerlukan kunci terurut dan aturan pembatalan iterator (iterator invalidation). Pilihlah berdasarkan nilai n sebenarnya, rasio penulisan, dan batas toleransi latensi.
Kompromi 3: Menggabungkan rentang bersebelahan atau mempertahankan asal-usul (provenance)
Penggabungan mengurangi jumlah entri dan menyederhanakan kueri. Jika interval mewakili izin, reservasi, atau periode akuntansi yang batasan aslinya penting, pertahankan metadata sumber atau gunakan representasi yang tidak membuang segmen.
Latihan kegagalan dan rencana evolusi
Latihan 1: Banyak penyisipan bersebelahan
Sisipkan 10.000 interval yang bersebelahan dalam urutan terbalik. Verifikasi bahwa tersisa satu interval yang ternormalisasi tanpa ada titik ujung yang hilang, lalu ukur pergeseran array untuk memutuskan apakah tree diperlukan.
Latihan 2: Penyisipan dan penghapusan acak
Hasilkan operasi add, remove, contains, dan overlaps secara acak lalu bandingkan dengan model pointwise. Periksa terutama bahwa penghapusan di bagian tengah suatu interval dan penyisipan di kemudian hari berhasil menggabungkan kedua sisi dengan benar.
Latihan 3: Kasus batas dan input tidak valid
Uji l == r, l > r, bilangan bulat yang sangat besar, dan NaN. Tentukan apakah rentang kosong langsung dikembalikan, rentang terbalik menghasilkan galat atau ditukar, dan input floating-point ditolak.
Kesalahan umum dan tindak lanjut
Kesalahan 1: Membingungkan antara bersebelahan dan tumpang tindih
Interval setengah terbuka [0,1) dan [1,2) tidak berpotongan, meskipun set yang ternormalisasi mungkin tetap menggabungkannya. Definisikan kondisi perpotongan dan penggabungan secara terpisah.
Kesalahan 2: Hanya memeriksa tetangga sebelah kanan
Pendahulu dapat melintasi titik akhir kiri yang baru. Periksa satu pendahulu setelah melakukan binary search.
Kesalahan 3: Meninggalkan interval kosong setelah penghapusan
Saring setiap selisih dengan start >= end, jika tidak contains dapat melaporkan kemunculan semu (phantom hit).
Kesalahan 4: Mengklaim bisect membuat penyisipan bernilai O(log n)
Python secara eksplisit mencatat bahwa pergeseran penyisipan list adalah O(n). Nyatakan biaya pencarian, pergeseran, dan pemindaian secara terpisah.
Kesalahan 5: Mengabaikan batasan floating-point
NaN tidak mengikuti urutan normal, dan kesetaraan aproksimasi membuat ketersebelahan menjadi tidak stabil. Tentukan normalisasi presisi sebelum mengizinkan tipe float.
Kesalahan 6: Menghilangkan asal-usul data
Jika interval mewakili izin, reservasi, atau periode akuntansi, penggabungan dapat menghilangkan makna asalnya. Simpan metadata atau jangan gabungkan segmen-segmen tersebut.