DSA面接の質問

数百問を解いても、まだ準備不足だと感じるなら、それは練習の半分を取り違えている証拠であることが多いです。このセクションでは、実際に何が評価されているのかを明らかにし、練習の方向をそこに合わせられるようにします。

ライブ形式のデータ構造とアルゴリズムの面接では、次の四点が同時に評価されます。問題がどのパターンに属するかを見抜けるか、コードを書く前に方針を説明できるか、境界条件で実装が正しく動くか、そして声に出して計算量を説明できるかです。多くの候補者は三番目だけを重視して二番目を軽視し、説明のないまま正解にたどり着いて評価を下げられてしまいます。

この見抜くというステップこそ、パターン練習が量をこなす練習に勝る理由です。問題が本当に新しいことはほとんどなく、既存パターンの組み合わせにすぎません。最初の一分でこれは頻度マップ上のスライディングウィンドウだと言えるようになれば、あとは実装するだけです。言語や職種別の関連する問題集は面接問題ハブにまとまっています。

これらのパターンが、出題の大部分を占めます。それぞれを示すシグナルを見抜けるようになりましょう。

• ツーポインタ。ソート済み入力、ペアの和、インプレースの分割、回文判定。
• スライディングウィンドウ。制約条件下での最長または最短の連続部分配列。
• ハッシュマップによる集計。アナグラム、重複、頻度の比較、最初の一意な要素。
• 二分探索。ソート済み配列、および配列が未ソートの場合の答えの空間に対する二分探索。
• 幅優先探索と深さ優先探索。木、グリッド、連結成分、重みなし最短経路。
• ヒープと優先度付きキュー。上位k件の問題、ソート済みストリームのマージ、中央値の逐次計算。
• 区間。開始点でソートしたうえでのマージ、挿入、重なりの検出。
• 動的計画法。重複する部分問題：階段の上り方、コイン交換、編集距離、部分列。
• バックトラッキング。順列、組み合わせ、部分集合、制約充足パズル。
• グラフアルゴリズム。トポロジカルソート、Union-Find、重み付き最短経路。

面接官が実際に使う言い回しで示した代表的な出題例：

• 配列の中からある目標値に合計が一致する二つの数を見つけ、次に追加の空間を使わずに実装する。
• 重複する文字を含まない最長の部分文字列の長さを返す。
• 回転済みのソート配列が与えられたとき、対数時間で目標値を見つける。
• 重なり合う区間をマージし、なぜソートするコストに見合うのかを説明する。
• 二分木を反転させ、次にその最大深度を求める。
• 二分探索木を検証し、素朴なチェック方法では何を見落とすかを説明する。
• グリッド内の島の数を数え、次にメモリに収まらないほど大きなグリッドをどう扱うかを説明する。
• 出現頻度が上位k件の要素を見つけ、選んだデータ構造の理由を説明する。
• ある金額に対する最小のコイン枚数を求め、漸化式を述べる。
• 連結リストにサイクルがあるかを検出し、次にサイクルの開始ノードを返す。
• 二分木をシリアライズし、デシリアライズする。
• 履修の前提条件が与えられたとき、そのスケジュールが実行可能かどうかを判定する。

バックエンド職の新卒候補者が部分文字列の問題を出され、すぐにコードを書き始めます。コードはほぼ正しいのですが、面接官は面接時間の大半をそのコードが何をしているのか尋ねることに費やし、評価にはバグではなく沈黙が反映されてしまいます。一方、四十秒かけて文字マップ上のウィンドウで、右端を広げ、重複が出たら左端を縮め、最大値を記録すると説明した候補者は、最も取り返しのつかない部分をすでにクリアしています。

黙って解く練習は、誤った反射を身につけてしまいます。ライブ面接では説明とコーディングを同時に行うことが求められ、それはどちらか一方だけとは異なる別のスキルです。

変えるべきは問題集ではなく練習方法です。何かを書き始める前に、パターン、方針、想定される計算量を声に出して述べましょう。説明を続けながらコードを書きます。書き終えたら、もう一度計算量を述べ、自分で対応したエッジケースを一つと、確認したいエッジケースを一つ挙げます。これを十問行う方が、黙って五十問解くよりも面接力を高めます。

模擬面接セッションでは、一人では練習できない追加質問が出題され、自分の説明を録音して後で見直すこともできます。ここには常に一つの正直な制約があります。監視付きのブラウザ内タイピング形式の評価テストは会話ではなく、ライブアシスタントが関わるべきものではありません。どのコーディング形式がライブでどれが自動評価かは、面接タイプハブで確認できます。