プロンプトとスコープ
add([l,r))、remove([l,r))、contains(x)、overlaps([l,r)) を備えた区間セットを実装してください。隣接または重複する区間は自動的にマージされ、削除によって区間が分割される場合があります。開境界と閉境界、空の範囲、および計算量について説明してください。
これは、順序付きコレクション、不変条件、および境界処理をテストします。Python の bisect のドキュメントには、二分探索で挿入位置を見つけることができるものの、リストへの挿入は依然として O(n) になる可能性があると記載されています。すべての操作が O(log n) であると主張するのではなく、データサイズの前提とツリー構造が必要かどうかを明記してください。
面接官がテストしていること
第一に、半開区間のセマンティクスを正しく定め、隣接関係を処理できるか。第二に、すべての区間ではなく、交差する可能性のある隣接区間のみを挿入・削除時に走査できるか。第三に、規模に応じて配列、平衡木、または区間木を選択し、不変条件を証明できるか。
回答前に確認すべき明確化のための質問
- 区間は閉区間、開区間、それとも半開区間ですか？
[l,r)と仮定し、[0,1)と[1,2)は交差しないものとします。 - 端点は浮動小数点数ですか？ 比較可能な整数と仮定します。そうでない場合は精度と NaN のルールを定義します。
- 隣接する区間はマージすべきですか？ 正規化された表現を維持するため、マージすると仮定します。
- 規模と読み取り/書き込みの比率はどのくらいですか？ 小規模なセットではソート済み配列を使用でき、大規模なセットでは平衡木や区間木が必要になる場合があります。
- 存在しない範囲を削除するとどうなりますか？ 冪等であり、存在する部分のみを保持すると仮定します。
30秒の回答フレームワーク
「半開区間を使用し、ソートされ、互いに素で、隣接しない状態を維持します。add は二分探索を使用して交差する可能性のある最初の位置を見つけ、右に走査して重複または隣接するエントリをマージします。remove は交差部分を走査し、空でない左右の残余を保持します。contains は先行区間を確認し、overlaps は終了点がクエリの開始点を超える最初の区間を確認します。配列は O(log n) の探索を持ちますが O(n) のシフトが発生します。より大規模なセットには、平衡木または区間木を使用します。」
ステップごとの詳細解説
ステップ 1: 正規化された不変条件の定義
ソートされ、互いに素で、隣接しない半開区間 [l,r)（ただし l < r）を格納します。空の区間は格納されません。正規化後、ある点は最大で1つの区間にしか属さないため、更新は局所的な隣接区間に集中できます。
ステップ 2: ストレージの選択
数千個の区間かつ書き込みが少ない場合は、ソート済み配列がシンプルで信頼性があります。二分探索で位置を特定し、挿入や削除で要素をシフトします。書き込みとクエリの量が多い場合は、順序付きキーの平衡木を使用します。カバレッジカウントや最大重複深度が必要な場合にのみ、拡張区間木を追加します。
ステップ 3: 挿入時の隣接区間の特定
bisect_left を使用して l 以上の最初の開始点を見つけ、l をまたいで伸びている可能性があるため、1つ前の区間を検査します。次の開始点が現在のマージ後の終了点以下である間、右に走査します。隣接する区間もマージに含まれます。
add(l, r):
i = first index with start >= l, then i = max(0, i - 1)
while i < len(intervals) and intervals[i].end >= l:
l = min(l, intervals[i].start)
r = max(r, intervals[i].end)
delete intervals[i]
insert [l, r) at iステップ 4: 削除と分割の実装
[l,r) と交差する可能性のある最初の区間を見つけ、次の開始点が少なくとも r になるまで処理します。各区間について、[start,l) と [r,end) の空でない部分を保持します。入力は正規化されているため、削除によって再マージが必要な隣接範囲が生成されることはありません。
ステップ 5: 点クエリと範囲クエリの実装
contains(x) については、start <= x を満たす最後の区間を見つけ、x < end を確認します。overlaps([l,r)) については、end > l を満たす最初の区間を見つけ、start < r であれば重複します。空のクエリ範囲は false を返します。すべての比較は半開区間のセマンティクスに従います。
ステップ 6: 正当性の証明
挿入ループは、新しい範囲と重複または接触する範囲のみを削除し、その和集合を1つの区間に置き換えるため、カバレッジが維持されます。削除は交差部分のみを削除し、2つの差分を保持します。各操作後にソート順と非隣接性が復元され、各クエリは1つの先行または後続候補のみを必要とします。
ステップ 7: 計算量の分析
配列の特定は O(log n) ですが、マージされたエントリのシフトと削除は O(n) になる可能性があります（n は区間数）。k 個の隣接区間の走査により O(k) が追加されます。平衡木を使用すると、実装とメモリのコストが増加する代わりに、O(log n + k) の局所的更新を提供できます。二分探索のコストと操作全体のコストを混同しないでください。
ステップ 8: 境界テストの設計
空のセット、空の範囲、隣接マージ、完全な包含、部分的な重複、複数区間にまたがるケース、中間削除、端点削除、負の数、繰り返しの操作、および大きなクエリ範囲をテストします。ランダムな操作をポイントごとのブール配列モデルと突き合わせて差分テストを行います。
トレードオフと境界
トレードオフ 1: 半開区間か閉区間か
半開区間は自然に合成でき、長さが r-l となり、時間や配列インデックスのユースケースに適しています。閉区間の業務要件では、隣接条件、長さ、および整数オーバーフローのルールを一貫して変更する必要があります。比較演算子のみを変更することは安全ではありません。
トレードオフ 2: 配列か平衡木か
配列はコードが短く、読み取りが多く小〜中規模のセットに対してキャッシュ効率が優れています。ツリー構造は多数の挿入と削除を処理できますが、順序付きキーとイテレータの無効化ルールが必要です。実際の n、書き込み比率、およびレイテンシの許容範囲に基づいて選択してください。
トレードオフ 3: 隣接範囲のマージか来歴の保持か
マージするとエントリ数が減少し、クエリが単純化されます。区間が元の境界が重要な権限、予約、または会計期間を表している場合は、ソースメタデータを保持するか、セグメントを破棄しない表現を使用してください。
障害訓練と発展計画
訓練 1: 多数の隣接挿入
10,000 個の隣接する区間を逆順に挿入します。端点の欠落がなく正規化された1つの区間が残ることを確認し、配列のシフトを測定してツリーが必要かどうかを判断します。
訓練 2: ランダムな挿入と削除
ランダムな add、remove、contains、overlaps の操作を生成し、ポイントごとのモデルと比較します。特に、1つの区間の中間を削除し、後から挿入した際に両側が正しくマージされることを確認します。
訓練 3: 境界および無効な入力
l == r、l > r、非常に大きな整数、および NaN をテストします。空の範囲で復帰するか、逆順の範囲でエラーを出すか入れ替えるか、浮動小数点入力を拒否するかどうかを定義します。
よくある間違いとフォローアップ
間違い 1: 隣接と重複の混同
半開区間の [0,1) と [1,2) は交差しませんが、正規化されたセットでは依然としてマージされる場合があります。交差条件とマージ条件は分けて定義してください。
間違い 2: 右の隣接区間のみを確認すること
先行区間が新しい左端点をまたいでいる可能性があります。二分探索の後には1つ前の区間も検査してください。
間違い 3: 削除後に空の区間を残してしまうこと
すべての差分を start >= end でフィルタリングしてください。そうしないと contains が誤ったヒットを報告する可能性があります。
間違い 4: bisect により挿入が O(log n) になると主張すること
Python では、リスト挿入のシフトが O(n) であることが明記されています。探索、シフト、走査のコストを分けて説明してください。
間違い 5: 浮動小数点の境界を無視すること
NaN は通常の順序に従わず、近似等価性によって隣接関係が不安定になります。浮動小数点数を許可する前に精度の正規化を定義してください。
間違い 6: 来歴情報の破棄
区間が権限、予約、または会計期間を表す場合、結合によって元の意味が失われる可能性があります。メタデータを保持するか、それらのセグメントをマージしないようにしてください。