プロンプトとコンテキスト
push、pop、top、getMin を持つスタックを実装してください。すべての操作は O(1) である必要があり、空スタック時の動作を明示しなければなりません。この設問はコーディング、バックエンド、ライブラリ開発の職種に適しています。重要なのは API を暗記することではなく、スタックの深さごとに最小値を維持することです。
面接官がテストしていること
不変条件
深さ d における補助構造体には、最初の d 個の値の最小値が格納されます。メインスタックと補助スタックは常に同じ長さを保ちます。
重複する最小値
新しい値が現在の最小値と等しい場合でも、それを記録する必要があります。そうしないと、1 つのコピーを pop したときに正しい最小値が失われます。
エラーと境界
空のスタックに対する pop、top、getMin には、例外、Option 型、エラーコードなど、一貫した規約が必要です。暗黙的な番兵値（sentinel）の使用は安全ではありません。
計算量
すべての操作はスタックのトップのみを対象とするため、時間計算量は O(1) であり、追加の空間計算量は O(n) です。getMin 時に走査を行う方法は要件を満たしません。
最初に確認すべき質問
- 空の操作は何を返すべきですか：例外、Option、それともエラーコードですか？
- 値は負の値、重複した値、または整数の制限値に近い値を取り得ますか？
- ジェネリックな比較演算子（comparator）が必要ですか、それとも整数のみですか？
- API は最小値のインデックスや出現回数を返すべきですか？
- スレッドセーフやロックフリーの実装は求められていますか？
- テストは個別の呼び出しを対象とすべきですか、それともランダムな操作シーケンスを対象とすべきですか？
30秒での回答
「同じ長さの 2 つのスタック（values と mins）を保持します。mins のトップには、現在存在するすべての値の最小値が格納されます。push 時には min(x, 現在の最小値) を push し、pop 時には両方を pop します。top と getMin は対応するトップを読み取ります。すべての操作は O(1) で、追加の空間計算量は O(n) です。重複する最小値を記録し、空スタックのエラー規約を定義し、低速な参照用リストに対してランダムなシーケンスを検証します。」
ステップごとの詳細な回答
ステップ 1: 不変条件を定義する
S を値スタック、M を補助スタックとします。すべての深さ d に対して、M[d] は S[0..d] の最小値と等しくなります。それらの長さは常に等しくなります。
ステップ 2: push を設計する
M が空でない場合は min(x, M.top()) を M に push し、空の場合は x を push します。その後、x を S に push します。新しい補助スタックのトップがプレフィックス最小値になります。
ステップ 3: pop とクエリを設計する
pop は両方のスタックから 1 つの要素を削除します。top は S.top() を読み取り、getMin は M.top() を読み取ります。走査は不要です。
ステップ 4: 重複を保持する
2, 1, 1 を push した後、M は 2, 1, 1 となります。1 回 pop しても依然として 1 を返さなければなりません。厳密に小さい値のみを記録すると、不変条件が崩れます。
ステップ 5: エラーと型を定義する
空のスタックは EmptyStackError をスローするか、型付けされた Result を返すことができます。ジェネリックな実装では、全順序の比較演算子を受け入れ、等価性を一貫して定義する必要があります。
ステップ 6: 計算量を証明しテストする
4 つの操作はすべて O(1) であり、補助空間は O(n) です。ランダムテストでは、通常のリストをオラクル（正解判定器）として保持し、各操作の後に top、最小値、サイズ、エラーを比較できます。
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
模範回答
「values と mins を保持します。mins[i] は values[0..i] の最小値であるため、2 つのスタックの長さは等しくなります。push は値とその新しいプレフィックス最小値を格納し、mins スタックが空の場合は値を直接格納します。pop は両方から削除し、top と getMin は対応するトップを読み取ります。
重複する最小値も格納する必要があります。2, 1, 1 の場合、mins は 2, 1, 1 となります。そうでなければ、1 回の pop で誤って 2 が返されてしまいます。空の操作には明示的なエラー規約を使用します。時間計算量は操作あたり O(1) で、追加空間は O(n) です。空、負の値、重複、交互の操作、およびランダムなシーケンスを、リストベースのオラクルに対してテストします。」
よくある間違い
- getMin 中に値スタックを走査してしまい、O(n) にしてしまう。
- 厳密に小さい値のみを記録し、重複する最小値を失ってしまう。
- メインスタックのみを pop して、データ構造間の同期を崩してしまう。
- pop 後に復元できない単一のグローバル最小値を保持してしまう。
- 空のスタックに対して 0 を返し、有効な入力と混同させてしまう。
- 負の値や整数の制限値を無視してしまう。
- 根拠なしにならし計算量（amortized bound）を厳密な O(1) と呼んでしまう。
- 比較演算子を定義せずにジェネリックオブジェクトへの対応を主張してしまう。
フォローアップ質問
フォローアップ 1: 1 つのスタックを使用できますか？
はい。各エントリに値とプレフィックス最小値のペアを格納します。不変条件は変わらず、空間計算量も O(n) のままです。
フォローアップ 2: getMax を追加するにはどうすればよいですか？
プレフィックス最大値スタックも保持するか、各エントリに値、min、max を格納します。時間計算量は操作あたり O(1) のままで、合計空間計算量は O(n) です。
フォローアップ 3: 最小値の個数を返すにはどうすればよいですか？
各補助エントリに min と count を格納します。等しい値の場合は count をインクリメントし、pop 時には前のエントリを復元します。重複とロールバックのセマンティクスを明示的に定義します。
フォローアップ 4: スレッドセーフにするにはどうすればよいですか？
各論理操作を囲む単一の mutex で両方のスタックを保護します。別々のロックを使用すると、不整合な中間状態が公開される可能性があります。ロックフリー設計には、アトミックな複合状態とメモリ再利用（memory reclamation）に関する議論が必要です。
フォローアップ 5: 正当性をどのように証明しますか？
帰納法を使用します。空のスタックは不変条件を満たします。push は新しいプレフィックス最小値を計算し、pop は以前の記録を復元します。したがって、getMin は常に現在の値スタックの最小値を返します。