1. 題幹與適用情境
實作單游標文字編輯器的核心緩衝區。邏輯文字是一串字元，游標位於兩個字元之間。支援 left()、right()、insert(ch)、delete() 與 text()。
儲存使用帶有未使用區間的陣列，這個區間稱為 gap。gapStart 為包含端，gapEnd 為排除端。可見文字是 gapStart 之前的前綴，加上 gapEnd 及之後的後綴。ETH Zurich 的練習使用這套表示，並要求驗證行為與邊界。公開的 Google L4 面經也提到 Text Editor/Bookkeeping 實作題，關注資料結構取捨、手動演算和準確複雜度。
2. 面試官考察點
- 狀態建模： 能否準確說明兩個索引，不混淆邏輯長度與陣列容量。
- 不變量： 每個操作和擴容是否都保持邊界合法以及同一份邏輯文字。
- 邊界紀律： 是否明確處理空緩衝區、滿 gap、左右端點與單字元文字。
- 複雜度推理： 能否解釋相鄰編輯為何便宜，以及長距離移動為何和距離線性相關。
- 設計判斷： 能否說明大檔案、多游標或協同編輯何時讓 Gap Buffer 不再合適。
弱回答先寫陣列移動，之後才發現越界。強回答從表示法推導每次移動，並用簡單字串模型測試。
3. 回答前需要澄清的問題
游標是字元索引還是邊界？
採用邊界定義：cursor 等於游標左側的邏輯字元數。如此 cursor=0 是左端，cursor=length 是右端，delete() 可定義為刪除游標左側的字元。
delete 表示游標前刪還是游標後刪？
確認是 Backspace 還是 Delete。本文採用 Backspace：讓 gap 向左擴展一個字元。若是向前刪除，則應消耗 gap 右側的第一個字元。
儲存與文字模型有什麼要求？
釐清按位元組還是 Unicode 標量值處理、文件最大大小，以及是否需要復原、隨機行定位、多游標或並行編輯。這些要求可能改變資料結構，而不只是增加方法。
4. 30 秒回答框架
「我會在陣列中維護一個位於游標處的 gap。gapStart 是游標邊界，gapEnd 是第一個後綴字元；邏輯文字是前綴加後綴。插入寫入 gapStart 並遞增它。退格把一個前綴字元移過 gap，同時遞減兩個索引。右移把一個後綴字元複製到前綴側，再遞增兩個索引。gap 為空時擴容。每個操作後用字串模型檢查邊界與等價性。相鄰編輯是攤銷 O(1)；移動 gap 和距離線性相關，因此大檔案或多游標情境可能需要 piece table 或 rope。」
5. 分步驟深入解答
步驟一：寫出表示不變量
容量為 n 時必須滿足 0 ≤ gapStart ≤ gapEnd ≤ n。邏輯長度為 n - (gapEnd - gapStart)。邏輯序列是 buffer[0:gapStart] 與 buffer[gapEnd:n] 的串接。gap 內的值被忽略，不必初始化。
步驟二：左移
若 gapStart == 0，游標已在左端。否則先遞減 gapStart 和 gapEnd，再把原本位於游標左側的字元複製到新的 gap 尾部。前綴少一個字元，序列順序保持不變。
步驟三：右移
若 gapEnd == n，游標已在右端。否則把 buffer[gapEnd] 複製到 buffer[gapStart]，然後遞增兩個索引。第一個後綴字元跨過 gap，順序不變。當 gap 只有一個槽位時，複製和更新索引的順序尤其重要。
步驟四：插入
若 gapStart == gapEnd，先呼叫 grow()。把字元寫入 buffer[gapStart]，再遞增 gapStart。新字元成為原游標邊界處前綴的最後一項。
步驟五：向後刪除
若 gapStart == 0，左側沒有字元。否則遞減 gapStart，被刪除字元就進入 gap。無需移動陣列，邏輯序列只減少前綴末尾字元。
步驟六：保持文字不變地擴容
配置更大陣列，把前綴複製到相同索引，並把後綴複製到新陣列尾部。保持 gapStart 不變，設定新的 gapEnd 使後綴長度不變。容量按幾何比例增長可讓 gap 附近插入達到攤銷常數時間，但記憶體限制可能要求更小的增長因子。
步驟七：有依據地選擇下一種結構
單游標、局部編輯適合 Gap Buffer，因為熱點區域保持連續。piece table 保留原始緩衝區與只追加的新緩衝區，適合強調復原的編輯器。rope 或分塊樹適合大文件與分散位置的編輯。協同編輯還需要操作轉換或 CRDT，Gap Buffer 本身無法解決合併語意。
6. 高品質示範回答
「我把游標建模成邊界，並在陣列中維護兩個索引包圍的未使用 gap。不變量是 0 ≤ gapStart ≤ gapEnd ≤ capacity；邏輯文字是 gap 前綴與 gap 後綴的串接。插入消耗一個 gap 槽位。退格遞減 gapStart；右移把一個後綴字元複製到前綴側並遞增兩個索引；左移做反向複製。gap 為空時，將後綴複製到新陣列尾部並擴容，邏輯序列不會改變。
我會用字串和游標組成的簡單模型做對照測試，覆蓋空緩衝區、滿 gap、兩端、單字元、反覆往返和擴容。局部編輯是攤銷 O(1)；移動游標每跨一個字元是 O(1)，長距離移動和擴容分別是線性成本。大檔案、多游標或協同編輯應考慮 piece table 或 rope，因為單一連續 gap 會成為瓶頸。」
7. 常見錯誤
- 把
gapEnd當成包含端 → 複製或邊界檢查多一個單元 → 明確 gap 是[gapStart, gapEnd)，並測試空 gap。 - 先遞增再右移 → 讀取錯誤的後綴單元 → 先複製
buffer[gapEnd]到buffer[gapStart]，再更新索引。 - 刪除時只清空陣列單元 → 邏輯長度和游標不變 → 透過遞減
gapStart擴大 gap。 - 擴容只移動 gap → 可能改變順序或遺失後綴 → 把後綴整體複製到新陣列尾部。
- 不約定位元組或字元 → 可能拆開多位元組字元 → 實作前宣告位元組還是標量值語意。
- 聲稱所有編輯都是
O(1)→ 忽略長距離移動和擴容 → 說明局部編輯的攤銷成本及線性情況。 - 用 Gap Buffer 直接做協同編輯 → 混淆本地儲存與合併語意 → 依需求選擇 piece table、rope 或 CRDT。
8. 追問及應對
如何實作向前 Delete？
若 gapEnd == capacity，游標後沒有字元。否則遞增 gapEnd；第一個後綴字元進入 gap 並從邏輯序列消失。這是 Backspace 的鏡像，保持同一不變量。
移動游標的最壞複雜度是什麼？
跨過 k 個字元要做 k 次常數時間複製，因此是 O(k)。從一端跳到另一端是 O(length)。如果編輯器經常跳到遠處，可加行索引或分塊結構降低導覽成本。
如何加入復原？
記錄編輯命令或逆向範圍，而不是保存整個陣列快照。piece table 可讓新增文字只追加並保留歷史參照；Gap Buffer 則需要明確操作日誌與游標位置。
如何驗證實作？
用 (string, cursor) 參考模型執行隨機操作序列。每次操作後比較 text()、游標位置與邊界，並斷言所有陣列存取都在容量內；ETH Zurich 練習明確要求驗證行為與邊界。