1. Masalah dan konteks
Implementasikan buffer inti untuk editor teks dengan kursor tunggal. Teks logis adalah urutan karakter; kursor berada di antara dua karakter. Dukung left(), right(), insert(ch), delete(), dan text().
Representasikan penyimpanan sebagai larik (array) dengan interval yang tidak terpakai yang disebut gap. Anggap gapStart inklusif dan gapEnd eksklusif. Teks yang terlihat adalah prefiks sebelum gapStart diikuti oleh sufiks pada dan setelah gapEnd. Latihan dari ETH Zurich menggunakan representasi ini dan meminta kandidat untuk memverifikasi perilaku serta batasannya. Laporan wawancara publik Google L4 juga menjelaskan sesi implementasi editor teks/pembukuan yang menekankan trade-off struktur data, dry run, dan kompleksitas yang akurat.
2. Apa yang dievaluasi oleh pewawancara
- Pemodelan status: Bisakah Anda menyatakan arti kedua indeks tanpa membingungkan panjang logis dan kapasitas larik?
- Invarian: Apakah setiap operasi dan pengubahan ukuran mempertahankan batas yang valid dan teks logis yang sama?
- Disiplin batas: Apakah buffer kosong, penuh, tepi kiri, tepi kanan, dan satu karakter ditangani secara eksplisit?
- Penalaran kompleksitas: Bisakah Anda menjelaskan mengapa pengeditan di dekat kursor berbiaya murah dan lompatan kursor yang jauh bersifat linier terhadap jarak?
- Pertimbangan desain: Bisakah Anda menyebutkan kapan gap buffer tidak lagi cocok untuk file besar, banyak kursor, atau pengeditan kolaboratif?
Jawaban yang lemah menulis pemindahan larik terlebih dahulu dan menemukan kesalahan off-by-one belakangan. Jawaban yang kuat menurunkan setiap pemindahan dari representasinya dan mengujinya terhadap model string sederhana.
3. Pertanyaan untuk diklarifikasi terlebih dahulu
Apakah kursor merupakan indeks karakter atau batas antar-karakter?
Gunakan batas antar-karakter: cursor sama dengan jumlah karakter logis di sebelah kirinya. Ini menjadikan cursor=0 sebagai tepi kiri dan cursor=length sebagai tepi kanan, serta mendefinisikan delete() sebagai penghapusan karakter tepat sebelum kursor.
Apa arti delete pada posisi kursor?
Konfirmasikan apakah yang dimaksud adalah Backspace atau Delete. Artikel ini menggunakan semantik Backspace: pindahkan gap ke kiri sebanyak satu posisi dan perbesar ukurannya. Operasi forward-delete sebaliknya akan memakan karakter pertama setelah gap.
Model penyimpanan dan teks apa yang diperlukan?
Klarifikasi antara byte versus nilai skalar Unicode, ukuran dokumen maksimum, dan apakah undo, pencarian baris acak, banyak kursor, atau pengeditan bersamaan diperlukan. Persyaratan tersebut dapat mengubah struktur data daripada hanya menambahkan metode.
4. Kerangka jawaban 30 detik
"Saya akan menyimpan dokumen dalam satu larik dengan gap pada posisi kursor. gapStart adalah batas kursor dan gapEnd menandai karakter sufiks pertama; teks logis adalah prefiks ditambah sufiks. Penyisipan menulis pada gapStart dan memajukannya. Backspace memindahkan satu karakter dari prefiks melintasi gap dan mengurangi kedua indeks. Bergerak ke kanan menyalin satu karakter sufiks ke sisi prefiks dan memajukan kedua indeks. Jika gap kosong, perbesar larik dan buat gap yang lebih besar. Saya akan menegaskan (assert) batasan dan kesetaraan model string setelah setiap operasi. Pengeditan lokal memiliki waktu konstan teramortisasi; memindahkan gap bersifat linier terhadap jarak, sehingga file besar atau banyak kursor mungkin memerlukan piece table atau rope."
5. Solusi langkah demi langkah
Langkah 1: Nyatakan invarian representasi
Untuk kapasitas n, harus memenuhi 0 ≤ gapStart ≤ gapEnd ≤ n. Panjang logisnya adalah n - (gapEnd - gapStart). Urutan logisnya adalah buffer[0:gapStart] yang digabungkan dengan buffer[gapEnd:n]. Nilai di dalam gap diabaikan dan tidak perlu diinisialisasi.
Langkah 2: Bergerak ke kiri
Jika gapStart == 0, kursor sudah berada di tepi kiri. Jika tidak, kurangi gapStart dan gapEnd, lalu salin karakter yang tepat berada sebelum kursor ke posisi gap terakhir yang baru. Prefiks kehilangan satu karakter dan sufiks tidak bertambah; karakter yang disalin sekarang secara logis berada sebelum gap.
Langkah 3: Bergerak ke kanan
Jika gapEnd == n, kursor berada di tepi kanan. Jika tidak, salin buffer[gapEnd] ke buffer[gapStart], lalu tambahkan kedua indeks. Karakter sufiks pertama melintasi gap, menjaga urutan sekuens. Urutan penyalinan dan pembaruan indeks sangat penting jika gap hanya memiliki satu slot.
Langkah 4: Menyisipkan (Insert)
Jika gapStart == gapEnd, panggil grow() sebelum menulis. Simpan karakter di buffer[gapStart] dan tambahkan gapStart. Karakter baru menjadi item terakhir di prefiks, tepat pada batas kursor sebelumnya.
Langkah 5: Menghapus ke belakang (Delete backward)
Jika gapStart == 0, tidak ada karakter di sebelah kiri. Jika tidak, kurangi gapStart; gap sekarang mencakup karakter yang dihapus. Tidak diperlukan pergeseran larik. Urutan logis kehilangan karakter prefiks terakhirnya.
Langkah 6: Menambah ukuran tanpa mengubah teks
Alokasikan larik yang lebih besar, salin prefiks ke indeks yang sama, dan salin sufiks ke ujung larik baru. Biarkan gapStart tidak berubah dan atur gapEnd yang baru sehingga panjang sufiks tetap konstan. Kebijakan kapasitas geometris seperti penggandaan memberikan waktu penyisipan konstan teramortisasi saat pengeditan tetap berada di dekat gap, tetapi batas memori dapat membenarkan faktor pertumbuhan yang lebih kecil.
Langkah 7: Pilih struktur berikutnya secara matang
Gap buffer sangat menarik untuk satu kursor aktif dan pengeditan lokal karena wilayah aktif tetap berdekatan (kontigu). Piece table mempertahankan buffer asli dan append-only, serta berguna untuk editor yang berorientasi pada undo. Rope atau pohon chunk menangani dokumen besar dan pengeditan yang tersebar di posisi-posisi yang berjauhan. Editor kolaboratif menambahkan persyaratan operational transformation atau CRDT yang tidak dapat diselesaikan oleh gap buffer.
6. Contoh jawaban berkualitas tinggi
"Saya memodelkan kursor sebagai batas dan mempertahankan dua indeks di sekitar gap yang tidak terpakai. Invariannya adalah 0 ≤ gapStart ≤ gapEnd ≤ capacity; teks logis adalah prefiks sebelum gap ditambah sufiks setelahnya. Penyisipan menggunakan satu slot gap. Backspace mengurangi gapStart, dan panah kanan menyalin satu karakter sufiks ke sisi prefiks sambil menambahkan kedua indeks. Panah kiri melakukan penyalinan simetris ke arah yang berlawanan. Ketika gap kosong, saya memperbesar penyimpanan dengan menyalin sufiks ke ujung baru, yang mempertahankan urutan logis.
Saya akan menguji operasi-operasi tersebut terhadap model string sederhana ditambah kursor, termasuk buffer kosong, gap penuh, kedua tepi batas, teks satu karakter, pembalikan berulang, dan penambahan ukuran. Pengeditan lokal memiliki biaya teramortisasi O(1); pergerakan kursor berbiaya O(1) per karakter yang dilewati, dan pengubahan ukuran berbiaya O(n). Untuk file besar, banyak kursor, atau pengeditan kolaboratif, saya akan beralih ke piece table atau rope karena satu gap kontigu akan menjadi bottleneck."
7. Kesalahan umum
- Memperlakukan
gapEndsebagai inklusif → Menyalin atau memeriksa batas satu sel terlalu jauh → Tentukan gap sebagai[gapStart, gapEnd)dan uji gap yang kosong. - Bergerak ke kanan setelah melakukan inkremen terlebih dahulu → Membaca sel sufiks yang salah → Salin
buffer[gapEnd]kebuffer[gapStart]sebelum mengubah indeks mana pun. - Menghapus dengan mengosongkan sel larik → Membiarkan panjang logis dan kursor tidak berubah → Perluas gap dengan mengurangi
gapStart. - Menambah ukuran hanya dengan memindahkan gap → Mengubah urutan atau menghilangkan sufiks → Salin sufiks sebagai satu blok ke ujung larik baru.
- Menggunakan byte tanpa kontrak tipe data → Dapat memecah karakter multi-byte → Deklarasikan semantik byte atau skalar sebelum mengimplementasikan pergerakan kursor.
- Mengklaim setiap pengeditan adalah
O(1)→ Mengabaikan pergerakan kursor yang jauh dan pengubahan ukuran → Nyatakan biaya pengeditan lokal teramortisasi serta kasus pergerakan/penambahan ukuran linier. - Menggunakan gap buffer untuk kolaborasi → Membingungkan penyimpanan lokal dengan semantik penggabungan (merge) → Pilih arsitektur piece table, rope, atau CRDT berdasarkan persyaratan kolaborasi.
8. Pertanyaan lanjutan
Bagaimana Anda akan mengimplementasikan forward Delete?
Jika gapEnd == capacity, tidak ada karakter setelah kursor. Jika tidak, tambahkan gapEnd; karakter sufiks pertama masuk ke dalam gap dan menghilang dari urutan logis. Ini adalah kebalikan dari Backspace dan mempertahankan invarian yang sama.
Apa kasus terburuk untuk menggerakkan kursor?
Bergerak melintasi k karakter melakukan penambahan k salinan dengan waktu konstan, sehingga biayanya adalah O(k). Melompat dari satu ujung ke ujung lainnya adalah O(length). Indeks baris atau struktur chunk dapat mengurangi beban navigasi ketika editor sering melompat ke posisi yang jauh.
Bagaimana Anda akan menambahkan fitur undo?
Catat perintah pengeditan atau rentang inversi daripada mengambil snapshot dari seluruh larik. Piece table dapat membuat teks yang disisipkan bersifat append-only dan menyederhanakan referensi riwayat, sedangkan gap buffer memerlukan log operasi eksplisit dan posisi kursor.
Bagaimana Anda memverifikasi implementasinya?
Jalankan serangkaian operasi acak terhadap pasangan referensi (string, cursor). Setelah setiap operasi, bandingkan text(), posisi kursor, dan batasannya. Tambahkan asersi bahwa setiap akses larik berada dalam kapasitas; latihan dari ETH Zurich secara eksplisit meminta verifikasi perilaku dan batas.