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 练习明确要求验证行为和边界。