AIコーディング面接問題：例と練習

アルゴリズム名を知っていても、新しい問題への取り組み方が分からないことはあります。以下の練習問題は、具体的な入力と解法の選択、計算量の上限、声に出して説明すべきエッジケースを結び付けます。

• Two Sum：値の合計が目標値になる、異なる2つの添字を返す。 [3, 3]、目標値6では、両方の位置を使用します。以前に確認した値のハッシュマップを使って走査し、現在の値を保存する前に補数があるか確認します。これにより、同じ添字の再利用を防げます。期待計算時間はO(n)、追加空間はO(n)です。組が存在しない場合に何を返すか確認してください。
• 同じ文字を含まない最長部分文字列を見つける。 'abba'では、長さは2です。各文字の最後の位置を記録し、重複のないウィンドウを維持します。以前の出現位置が現在のウィンドウ外にある場合、左端を後方へ戻してはいけません。ハッシュマップ参照を用いた期待計算時間はO(n)です。何を1文字として数えるか確認してください。
• 重なり合う閉区間を統合する。 [1, 3]、[3, 5]、[8, 10]では、[1, 5]と[8, 10]を返します。開始位置で並べ替え、現在の区間を延長するか、新しい区間を開始します。並べ替えにより計算時間はO(n log n)になります。端点を共有する閉区間は重なるため、それが問題の定義と一致するか尋ねてください。
• 閉路のない単方向連結リストを反転する。 現在のノードのnextポインタを変更する前に、次のノードを保存します。反復解法では計算時間がO(n)、追加空間がO(1)です。空のリスト、1ノード、2ノードの場合を追跡してください。各反復後に、リストのどの部分がすでに反転されているか説明しましょう。
• 二分木の値を階層ごとに返す。 キューを使い、次の階層へ進む前に現在の階層のノード数を処理します。計算時間はO(n)で、返却する出力を除く補助キュー空間はO(w)です。ここでwは階層の最大幅です。空の木と、各階層に子が1つだけある木をテストしてください。
• 前提科目が与えられたとき、すべての科目を履修できるか判定する。 前提科目を有向グラフとしてモデル化し、トポロジカルソートを使用します。処理された頂点がV個未満なら、有向閉路が残っています。計算時間はO(V + E)です。非連結成分、孤立した科目、自己依存をテストしてください。
• ある金額に達するために必要な最少の硬貨数を求める。 正の整数額面の硬貨を無制限に使えると仮定します。[1, 3, 4]、金額6では、最大の硬貨から選ぶと3枚必要ですが、3 + 3なら2枚です。動的計画法の状態を各金額に必要な最少硬貨数と定義し、金額ゼロに必要な硬貨ゼロから始めます。目標額A、額面数cの場合、標準的な方法の計算時間はO(Ac)、空間はO(A)です。到達不能な金額を明示的に処理してください。

職種やトピック別に整理された関連問題を練習するには、面接問題ライブラリをご覧ください。

次の問題を考えます：負の値を許容し、合計が目標値に等しい空でない連続部分配列を数える。 [1, -1, 1]、目標値1では、答えは3です。単一要素の[1]部分配列が2つ、または配列全体です。

まず基本解法として、各開始位置を選び、累積和を維持しながら終了位置を延ばします。計算時間はO(n²)、追加空間はO(1)です。負の値があると、ウィンドウを広げれば合計が増えるという前提が崩れるため、一般的な縮小ウィンドウ方式はここでは信頼できません。

より高速な方法では、接頭辞和と頻度マップを使用します。現在の接頭辞和がsなら、s - targetに等しい以前の接頭辞それぞれが、必要な合計を持つ部分配列を示します。配列開始前の空の接頭辞を表すため、接頭辞和ゼロの出現回数を1としてマップを初期化します。

• 処理順序： 現在の値を接頭辞和に加え、一致する以前の接頭辞を数えてから、現在の接頭辞を記録します。先に記録すると、目標値がゼロの場合に空の部分配列を誤って数えてしまいます。
• 不変条件： 現在の接頭辞を記録する前、マップには現在位置より前で終わるすべての接頭辞の頻度が含まれています。
• 計算量： 各要素で一定回数のマップ操作を行います。ハッシュ操作の期待計算時間が定数であると仮定すると、期待計算時間はO(n)、追加空間はO(n)です。
• 確認事項： 空の配列は0を返します。[0, 0]、目標値0では、3を返します。固定幅整数型では、累積和と答えの個数の両方でオーバーフローを考慮してください。

有用な追加質問は、問題が個数を求めているのか、実際の部分配列を求めているのかという点です。一致する部分配列をすべて返すと、出力コストが発生します。全要素がゼロの配列では、目標値がゼロの場合、空でない一致部分配列がn(n + 1)/2個あります。

助けを求める前に自分で試し、その後、先へ進むために必要な最小限の支援を求めましょう。以下のプロンプトを使えば、AIとの会話を検証可能な練習に変えられます。

• ヒントを1つ求める： どの情報を保存すべきかについて、ヒントを1つください。まだコードやアルゴリズムの正式名称は示さないでください。
• 推論を検証する： これが私のループ不変条件です。実装がこれに違反する入力を見つけるか、各更新で不変条件が保たれる理由を説明してください。 応答は自分で確認してください。モデルの同意は正しさの証明ではありません。
• 計算量を監査する： この実装で、スライス、並べ替え、コンテナ操作、再帰呼び出しによって行われる処理を数えてください。 よく知られたアルゴリズム名だけでは、実際のコードの計算量は確定しません。
• テストを生成する： 空の入力、重複、境界値、解が存在しない場合のテストケースを提案し、それぞれの期待結果を説明してください。 テストオラクルとして使う前に、それらの答えを自分でも導出してください。
• 制約を1つ変更する： 入力が並べ替え済み、変更不可、またはストリームとして到着する場合、解法はどう変わりますか？ コードを書き直す前に、新しいトレードオフを説明してください。

クラウド事業者のシニア職に備えるバックエンドエンジニアを考えてみましょう。前提科目グラフの問題を解いた後、彼女はAI練習パートナーに閉路を含む非連結グラフを求めます。その後、ヒントを見ずにキューを追跡し、処理済み頂点数によって閉路が明らかになる理由を説明します。

完全な解法を読んだ後は、それを閉じて、アルゴリズム、不変条件、テストを記憶から再構築してください。コードを再現できることよりも、なぜ機能するかを説明し、変更された制約に適応できることの方が重要です。

会話の中で推論を説明する練習をするには、模擬面接ページをご覧ください。

SubcueAIには2つのライブ支援画面があります。主力のmacOSおよびWindows向けネイティブアプリは、システム音声とマイク音声を取得し、ローカルのフローティングオーバーレイに支援内容を表示します。ZoomやMicrosoft Teamsなどのデスクトップ会議クライアントで動作します。

ブラウザー拡張機能も、ChromeやEdgeを含むChromiumブラウザーのSide Panelを通じてライブ支援を提供します。Google Meetのようなブラウザータブ通話に対応し、会議タブの音声だけを取得します。そのタブを通じて面接官の声を聞き取りますが、マイク音声は一切取得せず、候補者の発言も文字起こししません。Firefox版は模擬練習専用です。

どちらの画面も、通話に会議ボットを追加したり、会議ページへコンテンツスクリプトを挿入したりしません。コーディング問題では、音声による文脈と書面による文脈を区別してください。音声取得だけでは、エディターにのみ表示された問題文やコードは提供されません。すべての提案を、正確な問題文、制約、実装と照合してください。

ライブ支援を使用する前に、面接の規則を確認してください。 SubcueAIは、あらゆる状況で検知されないことを保証するものではありません。画面共有、録画、監督付き評価、会社管理端末は、秘匿保証の対象外です。共有画面や録画画面にはオーバーレイやSide Panelが映る可能性があり、端末管理機能や監督機能が操作を監視する場合もあります。

利用可能な各画面の設定方法については、SubcueAIチュートリアルをご覧ください。