問題と範囲
有界な整数全体集合 [0, U) が与えられたとき、insert(x)、remove(x)、contains(x)、clear()、および現在の要素に対するイテレーションを備えたセットを実装します。最初の 4 つの操作は最悪計算量 O(1) でなければならず、イテレーションは現在の要素数 k に対して O(k) かかります。重複は拒否され、存在しない値の削除は何もしない操作（no-op）となります。
公開されている面接記録には、Pure Storage のディスカッションでこの形式の質問が含まれています。中核となるテスト対象は、ライブラリクラスの暗記ではなく、dense/sparse 配列の不変条件です。
面接官がテストしていること
- 固定された全体集合が必要であると明言できるか。
O(1)という主張は、任意の整数に対して無条件に成り立つわけではありません。 dense[sparse[x]] == xを維持し、古いインデックスによる偽陽性を防ぐためにそれを利用しているか。- 削除時に末尾の要素と入れ替える（swap）ことで、dense のプレフィックスを連続した状態に保ち、イテレーションを
O(k)に維持できるか。 O(U)の空間計算量を述べ、ハッシュセットやビットマップのほうが適している状況を認識しているか。
コーディング前の確認事項
Uは既知であり、解法として長さUの配列を 2 つ割り当てることができますか？これがリソースの前提条件となります。iterate()はソートされている必要がありますか？この設計はすべての要素を返しますが、順序は保証しません。- イテレータの安定性や並行アクセスは必要ですか？これらの要件は、swap-delete や同期のセマンティクスを変更します。
clear()はUのスキャンを避ける必要がありますか？設問では定数時間が求められているため、sizeをリセットするだけにします。
30秒の回答
「長さ U の sparse インデックス配列、長さ U の dense 配列、そして現在の size を保持します。要素 x は、sparse[x] < size かつ dense[sparse[x]] == x であるときに限り正確に存在します。insert は dense[size] に x を書き込み、そのインデックスを記録します。remove はそのスロットを末尾の要素で上書きし、その要素のインデックスを修正します。clear は size を 0 に設定するだけです。4 つの中核操作は最悪計算量 O(1)、dense プレフィックスのイテレーションは O(k)、空間計算量は O(U) です。」
ステップごとの詳細解説
ステップ 1: 不変条件を明示する。
dense[0..size) は各要素を過不足なく 1 回ずつ含みます。要素 x に対し、sparse[x] は dense 内の位置であり、dense[sparse[x]] == x が成り立ちます。非要素には古い sparse の値が残っている可能性があるため、contains はインデックスが範囲内にあるかどうかだけを確認するのでは不十分です。
ステップ 2: 検索と挿入。
contains(x) は 0 <= x < U を確認し、次に sparse[x] < size と逆リンクを検証します。insert は最初に contains を呼び出し、存在しない場合は x を dense[size] に書き込み、sparse[x] = size を設定して、size をインクリメントします。
ステップ 3: Swap-delete（入れ替え削除）。
x が位置 i にある場合、last = dense[size - 1] とします。last を dense[i] に書き込み、sparse[last] = i を更新して、size をデクリメントします。sparse[x] をクリアする必要はありません。size が変化した後は、逆リンクのチェックによって古いエントリが無効化されるためです。末尾要素の削除も同じロジックに従います。
ステップ 4: 定数時間の clear と線形イテレーション。
clear() は size = 0 を設定します。古い配列の内容はもはや要素として読み取られません。イテレーションは dense[0] から dense[size - 1] までのみをスキャンするため、コストは O(U) ではなく O(k) となります。
ステップ 5: 計算量と境界条件。
contains、insert、remove、および clear は最悪計算量 O(1) です。イテレーションは O(k) であり、空間計算量は O(U) です。GCC のドキュメントでは、この表現方法は固定された全体集合やキャッシュ効率の良い列挙に有用であると記載されています。全体集合が不明である場合、拡大する必要がある場合、またはメモリに対して大きすぎる場合は、ハッシュセットやビットマップのほうが適している可能性があります。
ステップ 6: 不変条件のテスト。
すべてのランダムな操作を参照用の Set と比較します。空のセット、重複挿入、存在しない値の削除、中央および末尾の要素の削除、clear 後の再利用、値 0 および U-1 を網羅します。各操作の後に、dense プレフィックスに重複がなく、すべての要素の逆リンクが有効であることを検証します。
高品質な回答例
「有界な全体集合 [0, U) があることで、2 つの配列を引き換えに決定論的な定数時間操作を実現できます。dense は現在の要素のコンパクトなプレフィックスを格納し、sparse は値をその dense インデックスに対応付けます。所属判定では、境界、インデックス < size、および逆リンクを確認する必要があります。sparse の値だけを確認するのは安全ではありません。remove は末尾の要素を入れ替えてその sparse インデックスを更新し、clear は size のみをリセットします。更新と検索は最悪計算量 O(1)、イテレーションは O(k)、空間計算量は O(U) です。全体集合が制限されていない場合は、代わりにハッシュセットまたはビットマップを選択します。」
よくある間違い
sparse[x] < sizeのみを確認する → 存在しない値がもっともらしいインデックスを保持している可能性がある →dense[sparse[x]] == xも確認する。- 削除時に後続のすべての要素をシフトする → 削除が
O(U)またはO(k)になる → 末尾の要素と入れ替える。 - clear 時に配列を埋める → clear が
O(U)になる → size のみをリセットする。 - 有界な全体集合を無視する → 範囲外アクセスや許容できないメモリ消費が発生する → まず
[0, U)と容量を確認する。 - イテレーションを
O(1)と呼ぶ → ビューの取得は定数時間ですが、すべての要素を消費するのはO(k)です → 2 つのコストを区別する。
フォローアップの質問と回答
フォローアップ 1: 任意の整数をサポートするにはどうすればよいですか？
まず値を [0, U) に座標圧縮します。値の定義域が増え続ける場合や事前にスキャンできない場合はハッシュセットのほうが自然ですが、その定数時間は本設問の最悪計算量保証ではなく、ならし（amortized）または期待値（expected）になります。
フォローアップ 2: イテレーションの順序を保持するにはどうすればよいですか？
swap-delete は dense の順序を変更します。挿入順序を保持するには追加の連結リストまたは安定配列が必要となり、削除コストや空間コストが変化します。順序を追加する前に、それがインターフェース契約の一部であるかどうかを確認してください。
フォローアップ 3: ビットマップをどのような場合に選択しますか？
所属判定のみが操作であり、全体集合が中規模で、値あたり 1 ビットであることが重要な場合にビットマップを選択します。高速な列挙も重要な場合は sparse set を選択します。適切な選択は U、濃度、およびアクセスパターンによって決まります。