Temu duga pengekodan: Laksanakan interval tree untuk pertanyaan pertindihan (overlap)

Prompt dan kes penggunaan

Interval tree sesuai untuk julat masa dinamik, tempahan dan penghunian sumber. Idea terasnya ialah balanced tree yang disusun mengikut titik akhir bawah, diaugmentasikan dengan titik akhir atas maksimum bagi setiap subpokok untuk melangkau cabang yang mustahil.

Perkara yang dinilai oleh penemu duga

• Sama ada sempadan selang tertutup dan pertindihan adalah betul.
• Sama ada maxEnd ditakrifkan dan dikekalkan dengan tepat.
• Sama ada augmentasi memangkas kerja daripada mengimbas setiap nod.
• Sama ada penyisipan, pemadaman dan putaran mengemas kini augmentasi.
• Sama ada duplikasi, pokok kosong, dan pemadaman yang tiada dikendalikan.
• Sama ada kekompleksan mengambil kira bilangan selang yang dilaporkan.

Penjelasan sebelum menjawab

• Adakah selang tertutup, terbuka, atau separuh terbuka?
• Adakah titik akhir merupakan integer, titik terapung, atau cap masa?
• Adakah selang pendua dibenarkan, dan adakah pemadaman menggunakan ID atau titik akhir?
• Adakah pertanyaan mesti mengembalikan setiap pertindihan atau hanya satu?
• Adakah penyisipan dalam talian, pemadaman dan pengimbangan kendiri diperlukan?
• Adakah hasil mesti disusun mengikut titik akhir bawah?

Rangka jawapan 30 saat

“Saya akan mengunci balanced tree mengikut titik akhir bawah dan menyimpan titik akhir atas serta maxEnd maksimum subpokok. Sesuatu pertanyaan melaporkan pertindihan semasa, memasuki subpokok kiri hanya apabila maxEnd miliknya boleh mencapai batas bawah pertanyaan, dan memasuki bahagian kanan hanya semasa titik akhir bawah semasa berada dalam batas atas pertanyaan. Operasi insert dan delete menggunakan operasi balanced-tree dan mengemas kini maxEnd di sepanjang laluan, mengira semula nod yang terjejas selepas putaran.”

Analisis mendalam langkah demi langkah

Langkah 1: Takrifkan pertindihan. [a,b] dan [c,d] tertutup bertindih tepat apabila a <= d dan c <= b; tolak a > b terlebih dahulu.

Langkah 2: Takrifkan nod. Simpan low, high, ID unik, anak, dan maxEnd; susun mengikut (low, id) supaya titik akhir yang sama kekal berbeza.

Langkah 3: Pangkas pertanyaan. Laporkan nod semasa apabila ia bertindih. Lakukan rekursi ke kiri hanya apabila left.maxEnd >= query.low, dan lakukan rekursi ke kanan hanya apabila low <= query.high semasa.

Langkah 4: Kekalkan augmentasi. maxEnd ialah nilai maksimum bagi high nod dan kedua-dua nilai anaknya. Kira semula hanya laluan yang terjejas selepas kemas kini dan putaran.

Langkah 5: Padam dengan selamat. Cari mengikut ID, lakukan pemadaman balanced-tree, dan kemas kini maxEnd ke atas dari laluan penggantian; kembalikan hasil eksplisit untuk ID yang tiada.

Langkah 6: Uji kes sempadan. Liputi titik akhir yang bersentuhan, pembendungan (containment), duplikasi, nilai negatif, selang titik, pokok kosong, dan output yang mengandungi setiap selang.

Langkah 7: Nyatakan kekompleksan. Balanced tree mempunyai ketinggian logaritma; pertanyaan ialah O(log n + k) untuk k selang yang dilaporkan, kemas kini ialah O(log n), dan ruang ialah O(n).

Contoh jawapan berkualiti tinggi

“Saya akan menggunakan red-black tree yang disusun mengikut (low, id), dengan setiap nod menyimpan high dan subpokok maxEnd. Bagi [q1,q2], laporkan apabila low <= q2 dan high >= q1; masuk ke anak kiri hanya apabila left.maxEnd >= q1, dan anak kanan hanya apabila low <= q2 semasa. Operasi insert dan delete mengemas kini nilai maksimum pada laluan, dan putaran mengira semula nod yang diputar serta nod induk. ID membezakan pendua. Saya menguji titik akhir tertutup dan output yang merangkumi semua. Pertanyaan ialah O(log n + k) dan kemas kini ialah O(log n).”

Kesilapan lazim

• Menggunakan low < q2 untuk pertindihan → titik akhir yang bersentuhan hilang → padankan jenis selang yang dipilih.
• Menyimpan hanya high setiap nod → pemangkasan adalah mustahil → kekalkan maxEnd subpokok.
• Melangkau augmentasi selepas putaran → pertanyaan seterusnya menjadi salah → kira semula nod yang terjejas.
• Mendakwa pertanyaan O(log n) → kos output ditinggalkan → nyatakan O(log n + k).
• Menulis ganti titik akhir yang sama → pemadaman dan output menjadi tidak stabil → gunakan ID unik atau kunci komposit.

Soalan susulan dan jawapan

Soalan susulan 1: Bagaimana jika pertanyaan adalah titik sahaja?

Gunakan [x,x] dan pemangkasan maxEnd yang sama. Jika titik akhir adalah integer kecil dan statik, nilaikan struktur diskret khusus.

Soalan susulan 2: Mengapa tidak mengimbas senarai sahaja?

Dengan banyak selang dan kemas kini yang berselang-seli, imbasan akan menyentuh semua nod. Pokok mengehadkan carian kepada laluan logaritma ditambah output yang dilaporkan.

Soalan susulan 3: Mengapa putaran mengekalkan maxEnd?

Ia hanya menukar subpokok tempatan; mengira semula nod yang terjejas dari bawah ke atas memulihkan definisi medan tersebut.

Soalan susulan 4: Bagaimanakah anda memadamkan selang pendua?

Tetapkan ID semasa penyisipan, kunci mengikut (low, ID), dan padam mengikut ID supaya selang titik akhir sama yang lain kekal.

Soalan susulan 5: Bagaimana pula dengan titik akhir titik terapung?

Takrifkan semantik NaN, kejituan dan kesamaan. Jika boleh, tukarkan kepada tick integer atau unit masa.

Soalan susulan 6: Bagaimanakah anda menjamin output yang disusun?

Penjelajahan in-order menyediakan susunan titik akhir bawah; jika pemangkasan mengubah susunan lawatan, kumpul dan susun, sambil menyatakan kos tambahan.

Soalan susulan 7: Mengapakah pemangkasan itu selamat?

Jika titik akhir maksimum subpokok kiri berada di bawah batas bawah pertanyaan, setiap selang di situ berakhir terlalu awal untuk bertindih, jadi melangkauinya adalah selamat.