Petunjuk dan konteks
Implementasikan struktur larik bilangan bulat dengan riwayat. Setiap pembaruan mengubah satu posisi, dan sebuah kueri dapat meminta jumlah interval tertutup pada versi lama mana pun. Versi lama harus tetap tidak dapat diubah (immutable). Jelaskan batas koordinat, kompleksitas waktu dan ruang, percabangan versi, dan pengujian.
Ini adalah pertanyaan struktur data yang sulit mengenai divide-and-conquer, pembagian struktural (structural sharing), pembaruan immutable, batasan, dan pembuktian kompleksitas. Asumsikan panjang larik tetap, pembaruan penugasan titik (point assignment), dan jumlah rentang interval tertutup [l, r]. Pembaruan rentang, penghapusan, atau penggabungan versi adalah ekstensi terpisah dan harus disebutkan sebelum diimplementasikan.
Apa yang sedang diuji oleh pewawancara
Pewawancara ingin Anda memperjelas bahwa persistensi membuat root lama tetap dapat dikueri; persistensi tidak menyalin seluruh pohon pada setiap pembaruan. Implementasi yang kuat membuat simpul baru di sepanjang jalur pembaruan, menggunakan kembali subpohon yang tidak tersentuh, dan menyimpan satu root per versi. Implementasi tersebut juga menyatakan konvensi interval, perilaku kueri kosong, penomoran versi, nilai negatif, batasan, dan batas ruang.
Pertanyaan untuk diklarifikasi terlebih dahulu
- Apakah panjang larik dan cakupan koordinat bersifat tetap, atau dapatkah koordinat dikompresi terlebih dahulu?
- Apakah pembaruan berupa penugasan nilai atau penambahan (increment), dan bisakah posisi yang sama diperbarui berulang kali?
- Apakah rentang bersifat tertutup atau setengah terbuka, dan apa yang harus dikembalikan oleh rentang kosong?
- Bisakah sebuah versi bercabang dari root lama mana pun, atau hanya menambahkan dari versi terbaru?
- Apakah diperlukan keamanan thread (thread safety), persistensi disk, atau pembagian lintas proses?
- Apakah kita memerlukan jumlah bilangan bulat eksak, pemeriksaan overflow, atau bilangan bulat besar (big integers)?
- Berapa batas versi dan batas total operasi?
Kerangka jawaban 30 detik
"Saya akan merepresentasikan setiap versi dengan root dari segment tree yang immutable. Pembaruan titik menyalin O(log n) simpul dari root ke daun, membagikan setiap subpohon saudara (sibling) yang tidak tersentuh, dan kueri turun dari root yang diminta, mengembalikan jumlah simpul untuk cakupan penuh. Larik root memungkinkan percabangan dari versi lama mana pun. Pembuatan membutuhkan O(n); setiap pembaruan dan kueri adalah O(log n); total ruang adalah pohon awal ditambah O(log n) simpul baru per pembaruan. Saya akan menguji percabangan, kasus batas, nilai negatif, dan kasus diferensial acak."
Jawaban langkah demi langkah
Nyatakan invarian terlebih dahulu: sebuah simpul mencakup interval tertutup tertentu [lo, hi], sum adalah jumlah interval tersebut dalam versinya, daun mencakup satu posisi, jumlah simpul internal sama dengan jumlah anak-anaknya, dan simpul tidak pernah dimutasi setelah dibuat. Setiap versi menyimpan satu pointer root.
Untuk indeks larik 0..n-1, bangun secara rekursif. Jika input menggunakan koordinat bilangan bulat yang jarang dan besar, kumpulkan koordinat yang memungkinkan dan kompresi sebelum membangun; jangan mengalokasikan cakupan koordinat yang sangat besar secara langsung.
Pseudocode berikut menggunakan pembaruan penugasan dan kueri interval tertutup:
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] menyimpan pohon awal. Untuk memperbarui posisi i dari versi base, buat roots[next] = set(roots[base], 0, n - 1, i, value). Graf versi adalah struktur berbagi asiklik terarah (DAG) yang direferensikan oleh root, bukan rantai riwayat linier. Percabangan berarti memilih root lama mana pun sebagai input pembaruan.
Tangani batas secara eksplisit: untuk n == 0, jangan membuat root; indeks di luar rentang dan ql > qr harus mengembalikan kesalahan terstruktur atau mengikuti kontrak yang dinyatakan; memotong kueri tidak boleh menyembunyikan kesalahan pemanggil secara diam-diam. Hindari overflow lo + hi dengan menghitung lo + floor((hi - lo) / 2) ketika batas bilangan bulat bisa bernilai besar.
Konstruksi awal menggunakan O(n) simpul dan waktu. Pembaruan titik menyalin satu jalur dari root ke daun, sehingga membuat O(log n) simpul; kueri rentang mengunjungi O(log n) segmen kanonikal dan membutuhkan waktu O(log n). Setelah u pembaruan, total ruang adalah O(n + u log n), bukan O(nu). Penugasan atau penambahan rentang juga dapat menggunakan penyalinan jalur, tetapi tag lazy, kombinasi simpul, dan batas ruang akan berubah.
Imutabilitas adalah batas kebenaran. Jangan pernah memodifikasi sum atau pointer anak dari simpul lama selama pembaruan. Garbage collection atau reference counting dapat mereklamasi simpul; reklamasi manual harus mengetahui root versi mana yang tetap aktif, karena menghapus satu versi tidak dapat membebaskan simpul yang masih dibagikan oleh versi lain.
Jika hanya versi terbaru yang penting, segment tree normal lebih sederhana. Persistensi sepadan dengan biayanya untuk kueri riwayat, rollback, eksperimen percabangan, atau time travel. Untuk operasi yang sepenuhnya offline, metode prefix offline atau sweep-line mungkin lebih sederhana; hubungkan pilihan struktur data dengan beban kerja kueri.
Mulai pengujian dengan larik kecil. Setelah setiap pembaruan, salin larik biasa dan bandingkan versi serta rentang acak dengan struktur persisten. Cakup percabangan dari versi 0, pembaruan berulang pada satu posisi, nilai negatif, elemen tunggal, rentang penuh, titik tunggal, rentang kosong, dan kedua batas. Periksa juga pembagian simpul: setelah memperbarui satu posisi, subpohon yang tidak tersentuh harus mempertahankan identitas objek yang sama.
Uji imutabilitas secara langsung. Simpan semua hasil kueri versi lama, lakukan beberapa pembaruan bercabang, dan kueri kembali root lama; perubahan apa pun berarti simpul lama telah termutasi. Untuk beban kerja besar, hitung simpul yang dialokasikan dan konfirmasikan pertumbuhan mendekati O(n) awal ditambah O(log n) per pembaruan daripada salinan seluruh pohon yang tidak disengaja.
Contoh jawaban berkualitas tinggi
"Saya akan mengasumsikan larik dengan panjang tetap, pembaruan penugasan titik, jumlah interval tertutup, dan percabangan dari versi lama mana pun. Setiap simpul mencakup [lo, hi] dan menyimpan jumlahnya; simpul bersifat immutable setelah konstruksi. roots[v] menyimpan root untuk versi v.
Bangun secara rekursif. Saat pembaruan, salin jalur ke daun target: buat anak baru di sisi target, gunakan kembali pointer lama di sisi lain, dan buat setiap induk baru dari jumlah anak-anaknya. Kueri dari root yang diminta; kembalikan nol jika tidak ada tumpang tindih, kembalikan jumlah simpul untuk cakupan penuh, dan lakukan rekursi untuk kondisi lainnya.
Pembangunan membutuhkan waktu dan ruang O(n). Setiap pembaruan membuat O(log n) simpul, dan pembaruan maupun kueri membutuhkan O(log n); setelah u pembaruan, total ruang adalah O(n + u log n). Root lama tetap menunjuk ke simpul lama, sehingga versi historis tidak dapat terkontaminasi. Kompresi cakupan koordinat yang besar terlebih dahulu; untuk pembaruan rentang, evaluasi ulang tag lazy dan ruang.
Saya akan menguji percabangan dari versi 0, pembaruan berulang, nilai negatif, rentang kosong, dan setiap batas terhadap oracle larik biasa. Saya akan memverifikasi bahwa subpohon yang tidak tersentuh tetap dibagikan dan kueri lama tetap tidak berubah setelah pembaruan baru. Jika hanya nilai terbaru yang diperlukan, saya akan menggunakan segment tree reguler dan hanya menanggung biaya persistensi jika riwayat atau rollback merupakan kebutuhan nyata."
Kesalahan umum
- Menyalin seluruh pohon → setiap pembaruan menjadi O(n) ruang → hanya salin jalur dari root ke daun.
- Memutasi simpul lama dan menyimpan root baru → setiap versi lama yang membagikannya akan berubah → pertahankan simpul tetap immutable.
- Memperlakukan versi sebagai rantai linier → Anda tidak dapat bereksperimen atau melakukan rollback dari root arbitrer → biarkan larik root bercabang.
- Membiarkan konvensi interval implisit → rentang tertutup dan setengah terbuka menimbulkan bug batas → tetapkan satu konvensi dalam invarian dan signature.
- Mengalokasikan koordinat besar secara langsung → semesta koordinat dapat mengerdilkan titik sebenarnya → kompresi koordinat atau gunakan simpul dinamis.
- Mengklaim total ruang O(n) → setiap pembaruan menambahkan simpul jalur → nyatakan O(n + u log n).
- Membebaskan simpul secara rekursif saat menghapus versi → versi lain mungkin masih membagikannya → gunakan reference counting atau garbage collection.
Pertanyaan lanjutan dan jawaban
Pertanyaan lanjutan 1: Apakah struktur ini tetap berfungsi untuk penambahan rentang (range addition)?
Lakukan penyalinan jalur pada simpul yang disentuh oleh pembaruan dan salin setiap jalur yang relevan. Jika tag lazy digunakan, tag tersebut milik simpul baru dan tidak boleh ditulis ke dalam simpul yang dibagikan. Jumlah simpul baru dapat berkisar dari O(log n) hingga O(log n ditambah simpul yang dicakup), jadi berikan batasan untuk implementasi sebenarnya daripada menggunakan kembali klaim pembaruan titik.
Pertanyaan lanjutan 2: Bagaimana Anda mengueri perbedaan antara dua versi?
Telusuri kedua root secara bersamaan. Jika pointer simpul identik, subpohon tersebut tidak berubah dan dapat dilewati. Jika tidak, turun ke bawah atau hitung perbedaan agregat. Melaporkan setiap posisi yang diubah juga bergantung pada ukuran output.
Pertanyaan lanjutan 3: Mengapa tidak menyalin larik dan membangun prefix sum setiap kali?
Menyalin larik menghabiskan O(n) waktu dan ruang per pembaruan. Dengan sedikit versi dan larik kecil, metode yang lebih sederhana itu mungkin lebih unggul; persistensi menukar O(log n) ruang baru untuk banyak versi, kueri riwayat online, dan pembaruan lokal.
Pertanyaan lanjutan 4: Bagaimana cara menyimpan root versi secara persisten ke disk?
Beri ID stabil pada simpul, simpan ID anak alih-alih pointer memori, dan pertahankan tabel versi-ke-root. Gunakan penambahan (append) atau copy-on-write dan pastikan simpul baru bersifat tahan lama (durable) sebelum memublikasikan root. Pada pemulihan, validasi referensi dan tabel root; jangan pernah membuat serialisasi alamat memori mentah.
Pertanyaan lanjutan 5: Bagaimana Anda membuktikan bahwa versi lama tidak terkontaminasi?
Lakukan induksi atas pembaruan: hanya simpul baru yang dibuat, tidak ada field simpul lama yang berubah, dan pohon baru mereferensikan subpohon lama yang tidak tersentuh ditambah jalur baru. Oleh karena itu, simpul yang dapat dijangkau dari root lama dan nilainya tetap tidak berubah. Pengujian diferensial percabangan acak memvalidasi invarian ini dalam praktiknya.