1. Masalah dan konteks
Laksanakan penimbal teras bagi penyunting teks kursor tunggal. Teks logik ialah jujukan aksara; kursor berada di antara dua aksara. Sokong left(), right(), insert(ch), delete() dan text().
Wakilkan storan sebagai tatasusunan dengan selang tidak digunakan yang dipanggil jurang (gap). Anggap gapStart sebagai inklusif dan gapEnd sebagai eksklusif. Teks yang kelihatan ialah awalan sebelum gapStart diikuti oleh akhiran pada dan selepas gapEnd. Latihan ETH Zurich menggunakan perwakilan ini dan meminta calon mengesahkan kedua-dua tingkah laku dan batasan. Laporan temu duga awam Google L4 juga menerangkan pusingan pelaksanaan penyunting teks/simpan kira yang menekankan kompromi struktur data, ujian larian kering (dry runs) dan kejituan kekompleksan.
2. Perkara yang dinilai oleh penemu duga
- Pemodelan keadaan: Bolehkah anda menyatakan maksud kedua-dua indeks tanpa mengelirukan panjang logik dan kapasiti tatasusunan?
- Invarian: Adakah setiap operasi dan pensaizan semula mengekalkan batasan yang sah serta teks logik yang sama?
- Disiplin sempadan: Adakah penimbal kosong, penuh, tepi kiri, tepi kanan dan satu aksara dikendalikan secara eksplisit?
- Penaakulan kekompleksan: Bolehkah anda menerangkan sebab pengeditan berdekatan adalah murah dan lompatan kursor yang jauh adalah linear mengikut jarak?
- Pertimbangan reka bentuk: Bolehkah anda menyatakan bila gap buffer tidak lagi sesuai untuk fail besar, berbilang kursor atau penyuntingan kolaboratif?
Jawapan yang lemah menulis pemindahan tatasusunan terlebih dahulu dan menemui ralat off-by-one kemudian. Jawapan yang kukuh menerbitkan setiap pergerakan daripada perwakilan dan mengujinya terhadap model rentetan mudah.
3. Soalan untuk dijelaskan terlebih dahulu
Adakah kursor merupakan indeks aksara atau sempadan?
Gunakan sempadan: cursor bersamaan dengan bilangan aksara logik di sebelah kirinya. Ini menjadikan cursor=0 sebagai tepi kiri dan cursor=length sebagai tepi kanan, serta mentakrifkan delete() sebagai memadamkan aksara sejurus sebelum kursor.
Apakah maksud delete pada kursor?
Sahkan sama ada Backspace atau Delete yang dimaksudkan. Artikel ini menggunakan semantik Backspace: gerakkan jurang ke kiri sebanyak satu kedudukan dan besarkannya. Operasi pemadaman ke hadapan (forward-delete) sebaliknya akan menggunakan aksara pertama selepas jurang.
Apakah model storan dan teks yang diperlukan?
Jelaskan bait berbanding nilai skalar Unicode, saiz dokumen maksimum, dan sama ada buat asal (undo), carian baris rawak, berbilang kursor atau suntingan serentak diperlukan. Keperluan tersebut boleh mengubah struktur data dan bukannya sekadar menambah kaedah.
4. Rangka jawapan 30 saat
“Saya akan menyimpan dokumen dalam satu tatasusunan dengan jurang pada kursor. gapStart ialah sempadan kursor dan gapEnd menandakan aksara akhiran pertama; teks logik ialah awalan ditambah akhiran. Penyisipan menulis pada gapStart dan memajukannya. Backspace memindahkan satu aksara daripada awalan merentasi jurang dan mengurangkan kedua-dua indeks. Bergerak ke kanan menyalin satu aksara akhiran ke bahagian awalan dan memajukan kedua-dua indeks. Jika jurang kosong, besarkan tatasusunan dan cipta jurang yang lebih besar. Saya akan menegaskan (assert) batasan dan kesetaraan model rentetan selepas setiap operasi. Suntingan berdekatan mengambil masa malar terpelunasi (amortized constant time); memindahkan jurang adalah linear mengikut jarak, jadi fail besar atau banyak kursor mungkin memerlukan piece table atau rope.”
5. Penyelesaian langkah demi langkah
Langkah 1: Nyatakan invarian perwakilan
Bagi kapasiti n, syaratkan 0 ≤ gapStart ≤ gapEnd ≤ n. Panjang logik ialah n - (gapEnd - gapStart). Jujukan logik ialah buffer[0:gapStart] digabungkan dengan buffer[gapEnd:n]. Nilai di dalam jurang diabaikan dan tidak perlu dimulakan.
Langkah 2: Gerak ke kiri
Jika gapStart == 0, kursor sudah berada di tepi kiri. Jika tidak, kurangkan gapStart dan gapEnd, kemudian salin aksara yang berada sejurus sebelum kursor ke dalam kedudukan jurang terakhir yang baharu. Awalan kehilangan satu aksara dan akhiran tidak bertambah; aksara yang disalin kini secara logiknya berada sebelum jurang.
Langkah 3: Gerak ke kanan
Jika gapEnd == n, kursor berada di tepi kanan. Jika tidak, salin buffer[gapEnd] ke dalam buffer[gapStart], kemudian tingkatkan kedua-dua indeks. Aksara akhiran pertama merentasi jurang, mengekalkan susunan jujukan. Susunan penyalinan dan kemas kini indeks adalah penting apabila jurang mempunyai satu slot.
Langkah 4: Sisip (Insert)
Jika gapStart == gapEnd, panggil grow() sebelum menulis. Simpan aksara pada buffer[gapStart] dan tingkatkan gapStart. Aksara baharu menjadi item terakhir dalam awalan, tepat pada sempadan kursor yang sebelumnya.
Langkah 5: Padam ke belakang (Delete backward)
Jika gapStart == 0, tiada aksara di sebelah kiri. Jika tidak, kurangkan gapStart; jurang kini merangkumi aksara yang dialih keluar. Tiada anjakan tatasusunan diperlukan. Jujukan logik kehilangan aksara awalan terakhirnya.
Langkah 6: Besarkan storan tanpa mengubah teks
Peruntukkan tatasusunan yang lebih besar, salin awalan ke indeks yang sama, dan salin akhiran ke hujung tatasusunan baharu. Biarkan gapStart tidak berubah dan tetapkan gapEnd baharu supaya panjang akhiran kekal malar. Dasar kapasiti geometri seperti penggandaan memberikan penyisipan masa malar terpelunasi apabila suntingan kekal berhampiran jurang, tetapi had memori boleh mewajarkan faktor pertumbuhan yang lebih kecil.
Langkah 7: Pilih struktur seterusnya secara teliti
Gap buffer menarik untuk satu kursor aktif dan suntingan setempat kerana kawasan aktif kekal bersebelahan (kontigu). Piece table mengekalkan penimbal asal dan append-only, serta berguna untuk penyunting berasaskan buat asal (undo). Rope atau pepohon ketulan (chunks) mengendalikan dokumen besar dan suntingan yang tersebar merentasi kedudukan yang jauh. Penyunting kolaboratif menambah keperluan transformasi operasi atau CRDT yang tidak diselesaikan oleh gap buffer.
6. Contoh jawapan berkualiti tinggi
“Saya memodelkan kursor sebagai sempadan dan mengekalkan dua indeks di sekeliling jurang yang tidak digunakan. Invariannya ialah 0 ≤ gapStart ≤ gapEnd ≤ capacity; teks logik ialah awalan sebelum jurang ditambah akhiran selepasnya. Penyisipan menggunakan satu slot jurang. Backspace mengurangkan gapStart, dan anak panah kanan menyalin satu aksara akhiran ke bahagian awalan sambil meningkatkan kedua-dua indeks. Anak panah kiri melakukan salinan simetri ke arah bertentangan. Apabila jurang kosong, saya membesarkan storan dengan menyalin akhiran ke ekor baharu, yang mengekalkan jujukan logik.
Saya akan menguji operasi terhadap model rentetan mudah bersama kursor, termasuk penimbal kosong, jurang penuh, kedua-dua bahagian tepi, teks satu aksara, pembalikan berulang dan pembesaran saiz. Suntingan setempat adalah terpelunasi O(1); pergerakan kursor menelan kos O(1) bagi setiap aksara yang direntasi, dan pensaizan semula menelan kos O(n). Bagi fail besar, berbilang kursor atau suntingan kolaboratif, saya akan beralih kepada piece table atau rope kerana jurang kontigu tunggal menjadi kekangan utama (bottleneck).”
7. Kesilapan lazim
- Menganggap
gapEndsebagai inklusif → Menyalin atau menyemak batasan terlebih satu sel → Takrifkan jurang sebagai[gapStart, gapEnd)dan uji jurang kosong. - Bergerak ke kanan selepas meningkatkan indeks terlebih dahulu → Membaca sel akhiran yang salah → Salin
buffer[gapEnd]kebuffer[gapStart]sebelum mengubah mana-mana indeks. - Memadam dengan mengosongkan sel tatasusunan → Membiarkan panjang logik dan kursor tidak berubah → Kembangkan jurang dengan mengurangkan
gapStart. - Membesar dengan hanya memindahkan jurang → Menyusun semula atau kehilangan akhiran → Salin akhiran sebagai satu blok ke hujung tatasusunan baharu.
- Menggunakan bait tanpa kontrak yang jelas → Boleh memecahkan aksara pelbagai bait → Isytiharkan semantik bait atau skalar sebelum melaksanakan pergerakan kursor.
- Mendakwa setiap suntingan adalah
O(1)→ Mengabaikan pergerakan kursor yang jauh dan pensaizan semula → Nyatakan kos suntingan setempat terpelunasi dan kes pergerakan/pembesaran yang linear. - Menggunakan gap buffer untuk kolaborasi → Mengelirukan storan setempat dengan semantik penggabungan (merge) → Pilih seni bina piece table, rope atau CRDT berdasarkan keperluan kolaborasi.
8. Soalan susulan
Bagaimanakah anda akan melaksanakan forward Delete?
Jika gapEnd == capacity, tiada aksara selepas kursor. Jika tidak, tingkatkan gapEnd; aksara akhiran pertama memasuki jurang dan hilang daripada jujukan logik. Ini adalah cerminan bagi Backspace dan mengekalkan invarian yang sama.
Apakah kes terburuk untuk menggerakkan kursor?
Bergerak merentasi k aksara melakukan k salinan masa malar, jadi ia adalah O(k). Melompat dari satu hujung ke hujung yang lain ialah O(length). Indeks baris atau struktur berketul boleh mengurangkan kerja navigasi apabila penyunting kerap melompat ke kedudukan yang jauh.
Bagaimanakah anda akan menambah fungsi buat asal (undo)?
Catat arahan suntingan atau julat songsang berbanding mengambil snapshot keseluruhan tatasusunan. Piece table boleh menjadikan teks yang disisip bersifat append-only dan memudahkan rujukan sejarah, manakala gap buffer memerlukan log operasi eksplisit dan kedudukan kursor.
Bagaimanakah anda mengesahkan pelaksanaannya?
Jalankan surihan operasi rawak terhadap pasangan rujukan (string, cursor). Selepas setiap operasi, bandingkan text(), kedudukan kursor dan batasan. Tambahkan penegasan (assertions) bahawa setiap akses tatasusunan berada dalam lingkungan kapasiti; latihan ETH Zurich secara eksplisit meminta pengesahan tingkah laku dan batasan.