1. 問題とコンテキスト
単一カーソルテキストエディタ用のコアバッファを実装します。論理テキストは文字のシーケンスであり、カーソルは2つの文字の間に位置します。left()、right()、insert(ch)、delete()、および text() をサポートしてください。
ストレージは、ギャップと呼ばれる未使用の区間を持つ配列として表現します。gapStart を開始位置（inclusive）、gapEnd を終了位置（exclusive）とします。可視テキストは、gapStart より前のプレフィックスと、gapEnd 以降のサフィックスを連結したものです。チューリッヒ工科大学（ETH Zurich）の演習ではこの表現が使用されており、候補者に対して動作と境界の両方を検証することを求めています。公開されている Google L4 の面接レポートでも、データ構造のトレードオフ、ドライラン、および正確な計算量に重点を置いたテキストエディタ／記録管理の実装ラウンドが説明されています。
2. 面接官が評価するポイント
- 状態のモデリング: 論理的な長さと配列の容量を混同することなく、2つのインデックスが何を意味するかを述べられるか？
- 不変条件: すべての操作とリサイズが、有効な境界と同じ論理テキストを維持しているか？
- 境界条件への配慮: 空、満杯、左端、右端、および1文字のバッファが明確に扱われているか？
- 計算量の推論: 近傍での編集が低コストであり、カーソルの長いジャンプが距離に比例して線形になる理由を説明できるか？
- 設計判断: ギャップバッファが大きなファイル、複数のカーソル、または共同編集に適さなくなるタイミングを言及できるか？
不十分な回答では、最初に配列の移動コードを書いてしまい、後からオフバイワンエラーに気づくことになります。優れた回答では、データ表現から各移動を導き出し、シンプルな文字列モデルと照らし合わせてテストします。
3. 最初に明確にすべき質問
カーソルは文字インデックスですか、それとも境界ですか？
境界を使用します。cursor はその左側にある論理文字の数と等しくなります。これにより、cursor=0 が左端、cursor=length が右端となり、delete() はカーソルの直前にある文字を削除するものとして定義されます。
カーソル位置での delete は何を意味しますか？
Backspace と Delete のどちらが意図されているかを確認してください。この記事では Backspace のセマンティクス（ギャップを左に1つ移動して拡張する）を使用します。前方削除（forward-delete）操作の場合は、代わりにギャップの直後にある最初の文字を消費します。
どのようなストレージおよびテキストモデルが必要ですか？
バイト単位か Unicode スカラー値か、ドキュメントの最大サイズ、および Undo、ランダムな行検索、複数カーソル、または同時編集が必要かどうかを確認します。これらの要件によっては、単にメソッドを追加するだけでなく、データ構造そのものを変更する必要が生じる場合があります。
4. 30秒の回答フレームワーク
「ドキュメントをカーソル位置にギャップを持つ1つの配列として保持します。gapStart はカーソル境界であり、gapEnd はサフィックスの最初の文字を示します。論理テキストはプレフィックスとサフィックスの連結です。挿入時は gapStart に書き込み、それを進めます。Backspace はプレフィックスから1文字をギャップを越えて移動し、両方のインデックスをデクリメントします。右への移動はサフィックスの1文字をプレフィックス側にコピーし、両方のインデックスを進めます。ギャップが空になった場合は配列を拡張し、より大きなギャップを作成します。各操作の後に境界と文字列モデルとの等価性をアサートします。局所的な編集はならし定数時間です。ギャップの移動は距離に対して線形となるため、大きなファイルや多数のカーソルにはピーステーブルやロープが必要になる場合があります。」
5. ステップごとの解決策
ステップ1: 表現の不変条件を述べる
容量 n に対して、0 ≤ gapStart ≤ gapEnd ≤ n を満たす必要があります。論理的な長さは n - (gapEnd - gapStart) です。論理シーケンスは buffer[0:gapStart] と buffer[gapEnd:n] を連結したものです。ギャップ内の値は無視され、初期化の必要はありません。
ステップ2: 左へ移動
gapStart == 0 の場合、カーソルはすでに左端にあります。そうでない場合は gapStart と gapEnd をデクリメントし、カーソルの直前にあった文字を新しいギャップの末尾位置にコピーします。プレフィックスは1文字減り、サフィックスは増えません。コピーされた文字は論理的にギャップの前に位置するようになります。
ステップ3: 右へ移動
gapEnd == n の場合、カーソルは右端にあります。そうでない場合は buffer[gapEnd] を buffer[gapStart] にコピーし、両方のインデックスをインクリメントします。サフィックスの最初の文字がギャップを越え、シーケンスの順序が維持されます。ギャップが1スロットしかない場合、コピーとインデックス更新の順序が重要になります。
ステップ4: 挿入
gapStart == gapEnd の場合、書き込む前に grow() を呼び出します。文字を buffer[gapStart] に格納し、gapStart をインクリメントします。新しい文字はプレフィックスの最後の要素となり、カーソルの元の境界の正確な位置に入ります。
ステップ5: 後方削除
gapStart == 0 の場合、左側に文字はありません。そうでない場合は gapStart をデクリメントします。これでギャップに削除された文字が含まれるようになります。配列のシフトは不要です。論理シーケンスからプレフィックスの最後の文字が失われます。
ステップ6: テキストを変更せずに拡張する
より大きな配列を割り当て、プレフィックスを同じインデックスにコピーし、サフィックスを新しい配列の末尾にコピーします。gapStart は変更せず、サフィックスの長さが変わらないように新しい gapEnd を設定します。倍増などの幾何学的な容量ポリシーを採用すると、編集がギャップの近傍にとどまる限りならし定数時間での挿入が可能になりますが、メモリの制限によってはより小さな拡大倍率が妥当となる場合もあります。
ステップ7: 状況に応じて適切な構造を選択する
ギャップバッファは、ホットな領域が連続した状態に保たれるため、アクティブなカーソルが1つで局所的な編集を行う場合に適しています。ピーステーブルは元のバッファと追加専用バッファを保持し、Undo を重視するエディタに役立ちます。ロープやチャンクのツリーは、大きなドキュメントや離れた位置に分散した編集を処理できます。共同編集エディタでは、ギャップバッファでは解決できない操作変換（OT）や CRDT の要件が加わります。
6. 高品質な回答例
「カーソルを境界としてモデル化し、未使用のギャップを挟んで2つのインデックスを保持します。不変条件は 0 ≤ gapStart ≤ gapEnd ≤ capacity であり、論理テキストはギャップより前のプレフィックスとギャップより後のサフィックスの合計です。挿入はギャップのスロットを1つ消費します。Backspace は gapStart をデクリメントし、右矢印は両方のインデックスをインクリメントしながらサフィックスの1文字をプレフィックス側にコピーします。左矢印は逆方向に同様の対称コピーを行います。ギャップが空になった場合は、サフィックスを新しい末尾にコピーしてストレージを拡張し、論理シーケンスを維持します。
空のバッファ、満杯のギャップ、両端、1文字のテキスト、繰り返しの反転、拡張などを含め、単純な文字列＋カーソルモデルに対して操作をテストします。局所的な編集はならし O(1) です。カーソル移動のコストは通過する文字ごとに O(1) であり、リサイズのコストは O(n) です。大きなファイル、複数カーソル、または共同編集の場合は、単一の連続ギャップがボトルネックになるため、ピーステーブルやロープに切り替えます。」
7. よくある間違い
gapEndを inclusive として扱う → コピーまたは境界チェックが1セル分ずれる → ギャップを[gapStart, gapEnd)として定義し、空のギャップでテストする。- インクリメントした後に右移動を行う → 誤ったサフィックスセルを読み取ってしまう → いずれかのインデックスを変更する前に
buffer[gapEnd]をbuffer[gapStart]にコピーする。 - 配列セルをクリアすることで削除する → 論理的な長さとカーソルが変わらないままになる →
gapStartをデクリメントしてギャップを拡張する。 - ギャップのみを移動して拡張する → サフィックスの順序が変わったり失われたりする → サフィックスをブロックとして新しい配列の末尾にコピーする。
- 契約なしにバイトを使用する → マルチバイト文字を分断する可能性がある → カーソル移動を実装する前に、バイト単位かスカラー値かのセマンティクスを宣言する。
- すべての編集が
O(1)であると主張する → 長いカーソル移動やリサイズを無視している → 局所的な編集のならしコストと、線形になる移動／拡張のケースを述べる。 - 共同編集にギャップバッファを使用する → ローカルストレージとマージセマンティクスを混同している → 共同編集の要件に基づいて、ピーステーブル、ロープ、または CRDT アーキテクチャを選択する。
8. フォローアップの質問
前方 Delete（Deleteキー）はどのように実装しますか？
gapEnd == capacity の場合、カーソルの後に文字はありません。そうでない場合は gapEnd をインクリメントします。これによりサフィックスの最初の文字がギャップに入り、論理シーケンスから消えます。これは Backspace の鏡像であり、同じ不変条件を維持します。
カーソル移動の最悪ケースは何ですか？
k 文字を移動すると、k 回の定数時間コピーが実行されるため、O(k) になります。端から端へのジャンプは O(length) です。エディタが離れた位置に頻繁にジャンプする場合は、行インデックスやチャンク構造によってナビゲーション処理を削減できます。
Undo をどのように追加しますか？
配列全体のスナップショットではなく、編集コマンドや逆の範囲を記録します。ピーステーブルを使用すると、挿入されたテキストが追加専用となり履歴参照が単純になりますが、ギャップバッファでは明示的な操作ログとカーソル位置が必要になります。
実装をどのように検証しますか？
参照ペア (string, cursor) に対してランダムな操作トレースを実行します。各操作の後に、text()、カーソル位置、および境界を比較します。すべての配列アクセスが容量内にあるというアサーションを追加します。ETH Zurich の演習では、動作と境界の検証が明示的に求められています。