設問とコンテキスト
book(start, end) が true を返し、既存の区間と重複しない場合にのみ区間を保存するカレンダーを実装します。区間は半開区間であり、start < end である必要があります。[10, 20) と [20, 30) は隣接しています。この問題は、順序付き構造、境界、挿入のタイミング、および計算量をテストします。
面接官が見ているポイント
重要なのは証明可能な重複条件です。開始時刻がソートされていれば、直前の要素（predecessor）と直後の要素（successor）のみをチェックすれば十分です。優れた回答では、線形探索（scan）、平衡木、およびソート済み配列を比較し、さらにマルチスレッドや永続化サービスではアトミック性とロックの要件が加わることに言及します。
確認すべき質問
- 時刻は整数ですか、それともタイムスタンプですか？また負の値になり得ますか？
start < endのバリデーションは必須ですか？不正な入力に対してはどう対処しますか？- 区間は厳密な半開区間であり、等しい端点同士が接することは許容されますか？
- 予約の件数や範囲はどの程度ですか？キャンセルやクエリは必要ですか？
- これはメモリ内のシングルスレッドですか、それとも永続化されたマルチプロセスサービスですか？
30秒での回答
開始時刻で順序付けられたマップを使用します。[s, e) に対して、開始時刻が s 以上である最初の後続要素を見つけます。その開始時刻が e 未満であれば、区間は重複しています。次に先行要素を調べます。その終了時刻が s より大きければ重複しています。両方のチェックに合格した場合にのみ挿入します。半開区間のセマンティクスにより、先行要素の終了時刻が s と等しいこと、および後続要素の開始時刻が e と等しいことが許可されます。平衡木を使用すると、O(log n) の検索・挿入と O(n) の空間計算量が実現できます。
ステップごとの詳細な回答
ステップ 1: 重複を定義する
半開区間 [a, b) と [c, d) は、a < d && c < b のときにのみ正確に重複します。開始時刻が順序付けられていれば、より遠い区間はそれ以前に終了するかそれ以降に開始するため、直前と直後の要素を確認するだけで十分です。
ステップ 2: 順序付き構造を選択する
平衡木や Java の TreeMap は、先行要素と後続要素の検索機能を提供します。ソート済み配列は探索が O(log n) ですが挿入は O(n) であり、線形探索は O(n) です。予約量や操作の割合に応じて選択を適合させます。
ステップ 3: 挿入前にチェックする
後続要素、先行要素の順に検査し、両方が合格した後にのみ書き込みを行います。先に挿入してから後でロールバックすると、無効な中間状態が公開される可能性があります。
boolean book(int start, int end) {
if (start >= end) return false;
var next = events.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
var prev = events.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
events.put(start, end);
return true;
}ステップ 4: 境界の挙動を証明する
next.start == end と prev.end == start は重複しません。開始時刻が等しい場合、後続要素のチェックによって拒否されるため、交差する古い区間を置き換えることはできません。タイムスタンプがオーバーフローする可能性がある場合は、安全な数値型を使用してください。
ステップ 5: 計算量を明示する
平衡木での先行要素・後続要素の探索および挿入は O(log n) であり、空間計算量は O(n) です。ソート済み配列は O(log n) で探索しますが挿入は O(n) です。線形探索はシンプルですがスケールしません。計算量の議論には拒否された呼び出しも含めてください。
ステップ 6: 並行性と永続化への拡張
単一マシン上では、チェックと挿入をまとめてロックします。プロセスをまたぐ場合は、トランザクション、ユニーク制約、または範囲ロックを使用します。キャッシュを競合判定の最終的な権限にしてはなりません。
トレードオフと境界条件
半開区間と閉区間の比較
半開区間は隣接するスロットを自然に表現でき、長さは end - start となり、境界の重複を避けることができます。閉区間を採用するビジネスロジックでは、粒度を一貫して再定義する必要があります。
TreeMap と区間木の比較
すべての重複を拒否する場合は、先行要素と後続要素だけで十分です。重複クエリ、キャンセル、または範囲統計が必要な場合は、区間木（interval tree）やデータベースの範囲インデックスの採用が正当化される可能性があります。
導入計画とエビデンス
テストマトリクス
最初の区間、包含関係、部分的な重複、接する端点、等しい開始時刻、空の入力、大きな値、および重複リクエストを網羅します。受け入れられた予約のたびに、ソートされた不変条件をアサートします。
本番環境の境界
複数インスタンスの場合は、トランザクション分離レベル、競合エラー、リトライ用べき等性キー、およびタイムゾーン規則を定義します。並行予約の負荷テストを実施して、永続化制約を検証します。
よくあるミスと発展的な問い
ミス: 後続要素のみをチェックする
新しい区間は先行要素の末尾と重複する可能性があるため、先行要素の終了時刻もチェックする必要があります。
ミス: 等しい端点を重複として扱う
半開区間のセマンティクスでは、[10, 20) と [20, 30) が接することを許容します。厳密な比較を維持してください。
ミス: 競合を検出する前に挿入する
不変条件を維持するため、チェックと書き込みは単一の論理的アトミックステップでなければなりません。
発展: 2 つまでの重複を許容する
アクティブな区間のカウントを維持するかスイープライン法を使用します。制約は最大重複問題へと変わります。
発展: 並行予約
単一マシン上ではロックを使用します。インスタンス間では、プロセスローカルのメモリではなく、トランザクション、範囲ロック、またはシリアライザブルな書き込みを使用します。