Wawancara coding: Mengimplementasikan interval tree untuk query tumpang tindih (overlap)

Prompt dan kasus penggunaan

Interval tree cocok untuk rentang waktu dinamis, pemesanan (booking), dan okupansi sumber daya. Ide intinya adalah balanced tree yang diurutkan berdasarkan batas akhir bawah, diaugmentasi dengan batas akhir atas maksimum dari setiap subtree untuk melewati cabang yang tidak memungkinkan.

Apa yang dievaluasi pewawancara

• Apakah batas closed-interval dan tumpang tindih sudah benar.
• Apakah maxEnd didefinisikan dan dipelihara secara tepat.
• Apakah augmentasi memangkas pekerjaan alih-alih memindai setiap node.
• Apakah penyisipan, penghapusan, dan rotasi memperbarui augmentasi.
• Apakah duplikat, tree kosong, dan penghapusan data yang tidak ada ditangani.
• Apakah kompleksitas memperhitungkan jumlah interval yang dilaporkan.

Klarifikasi sebelum menjawab

• Apakah intervalnya tertutup (closed), terbuka (open), atau setengah terbuka (half-open)?
• Apakah batas akhirnya berupa integer, floating point, atau timestamp?
• Apakah interval duplikat diizinkan, dan apakah penghapusan menggunakan ID atau batas akhir?
• Apakah query harus mengembalikan semua overlap atau hanya satu?
• Apakah penyisipan online, penghapusan, dan self-balancing diperlukan?
• Apakah hasilnya harus diurutkan berdasarkan batas akhir bawah?

Kerangka jawaban 30 detik

“Saya akan mengunci balanced tree berdasarkan batas akhir bawah dan menyimpan batas akhir atas ditambah maxEnd maksimum subtree. Sebuah query melaporkan overlap saat ini, masuk ke subtree kiri hanya ketika maxEnd miliknya dapat mencapai batas bawah query, dan masuk ke sisi kanan hanya selama batas akhir bawah saat ini berada dalam batas atas query. Insert dan delete menggunakan operasi balanced-tree dan memperbarui maxEnd di sepanjang jalur, menghitung ulang node yang terpengaruh setelah rotasi.”

Pembahasan mendalam langkah demi langkah

Langkah 1: Definisikan overlap. [a,b] dan [c,d] tertutup tumpang tindih tepat ketika a <= d dan c <= b; tolak a > b terlebih dahulu.

Langkah 2: Definisikan node. Simpan low, high, ID unik, child, dan maxEnd; urutkan berdasarkan (low, id) agar batas akhir yang sama tetap berbeda.

Langkah 3: Pangkas query. Laporkan node saat ini ketika terjadi overlap. Lakukan rekursi ke kiri hanya ketika left.maxEnd >= query.low, dan rekursi ke kanan hanya ketika low <= query.high saat ini.

Langkah 4: Pelihara augmentasi. maxEnd adalah nilai maksimum dari high milik node dan kedua nilai child-nya. Hitung ulang hanya jalur yang terpengaruh setelah pembaruan dan rotasi.

Langkah 5: Hapus dengan aman. Cari berdasarkan ID, lakukan penghapusan balanced-tree, dan perbarui maxEnd ke arah atas dari jalur penggantian; kembalikan hasil eksplisit untuk ID yang tidak ditemukan.

Langkah 6: Uji batas. Cakup batas akhir yang saling bersentuhan, pembendungan (containment), duplikat, nilai negatif, interval titik, tree kosong, dan output yang memuat setiap interval.

Langkah 7: Nyatakan kompleksitas. Balanced tree memiliki tinggi logaritmik; query adalah O(log n + k) untuk k interval yang dilaporkan, pembaruan adalah O(log n), dan ruang adalah O(n).

Contoh jawaban berkualitas tinggi

“Saya akan menggunakan red-black tree yang diurutkan berdasarkan (low, id), dengan setiap node menyimpan high dan subtree maxEnd. Untuk [q1,q2], laporkan ketika low <= q2 dan high >= q1; masuk ke child kiri hanya ketika left.maxEnd >= q1, dan child kanan hanya ketika low <= q2 saat ini. Insert dan delete memperbarui nilai maksimum pada jalur, dan rotasi menghitung ulang node yang diputar beserta parent-nya. ID membedakan duplikat. Saya menguji endpoint tertutup dan output yang mencakup semua data. Query adalah O(log n + k) dan pembaruan adalah O(log n).”

Kesalahan umum

• Menggunakan low < q2 untuk overlap → batas akhir yang saling bersentuhan menghilang → sesuaikan dengan tipe interval yang dipilih.
• Hanya menyimpan high milik setiap node → pemangkasan menjadi mustahil → pelihara subtree maxEnd.
• Melewatkan augmentasi setelah rotasi → query berikutnya menjadi salah → hitung ulang node yang terpengaruh.
• Mengklaim query O(log n) → biaya output terlewatkan → nyatakan O(log n + k).
• Menimpa batas akhir yang sama → penghapusan dan output menjadi tidak stabil → gunakan ID unik atau composite key.

Pertanyaan lanjutan dan tanggapannya

Pertanyaan lanjutan 1: Bagaimana jika query hanya berupa titik?

Gunakan [x,x] dan pemangkasan maxEnd yang sama. Jika batas akhir berupa integer kecil dan statis, evaluasi struktur diskret khusus.

Pertanyaan lanjutan 2: Mengapa tidak memindai list saja?

Dengan banyak interval dan pembaruan yang diselingi, pemindaian akan menyentuh semua node. Tree membatasi pencarian ke jalur logaritmik ditambah output yang dilaporkan.

Pertanyaan lanjutan 3: Mengapa rotasi mempertahankan maxEnd?

Rotasi hanya mengubah subtree lokal; menghitung ulang node yang terpengaruh dari bawah ke atas memulihkan definisi field tersebut.

Pertanyaan lanjutan 4: Bagaimana cara menghapus interval duplikat?

Tetapkan ID saat penyisipan, gunakan (low, ID) sebagai kunci, dan hapus berdasarkan ID sehingga interval lain dengan batas akhir yang sama tetap ada.

Pertanyaan lanjutan 5: Bagaimana dengan batas akhir floating-point?

Definisikan semantik NaN, presisi, dan kesetaraan. Jika memungkinkan, konversikan ke tick integer atau satuan waktu.

Pertanyaan lanjutan 6: Bagaimana cara menjamin output yang terurut?

Penelusuran in-order memberikan urutan batas akhir bawah; jika pemangkasan mengubah urutan kunjungan, kumpulkan dan urutkan, dengan menyatakan biaya tambahannya.

Pertanyaan lanjutan 7: Mengapa pemangkasannya aman?

Jika batas akhir maksimum subtree kiri berada di bawah batas bawah query, setiap interval di sana berakhir terlalu dini untuk dapat tumpang tindih, sehingga melewatkannya aman.