面接質問と回答の解説 — ページ 51 / 52
Offer.ccの面接質問と回答解説の51ページ目を閲覧。思考プロセス、実装の詳細、深掘り質問、公開情報ソースを確認できます。
コーディング面接：配列内の k 番目に大きい要素を見つける
ソートやサイズ制限付きヒープから、正確なパーティション不変条件、重複要素の処理、計算量のトレードオフ、実行可能なテストを備えたランダム化3-wayクイックセレクトまで、k 番目に大きい要素の解法を導出します。
コーディング面接：ランダムポインタを持つ連結リストのコピー
同一性マップを用いてランダムポインタを持つ連結リストをディープコピーする方法を学び、さらにインターリーブ最適化を導出し、その不変条件を証明して元のリストを安全に復元する手法を理解します。
コーディング面接：ネットワーク内のすべての重要接続（Critical Connections）を検出する
発見時刻（discovery times）と low-link 値を用いて無向グラフのすべての橋（bridge）を検出し、厳密な橋の判定条件を証明した上で、コールスタック枯渇を防ぐ安全な反復型 DFS を実装します。
コーディング面接：k 個ごとのグループでノードを反転する（Reverse Nodes in k-Group）
ダミーノード、完全グループの先読み、および境界を定めたポインタ反転を用いて k 個ごとのノード反転を解き、不完全な末尾グループが変更されない理由を証明します。
コーディング面接：ヒストグラムで最大の長方形を求めるにはどうすればよいか？
最も近いより小さい境界からヒストグラム内の最大長方形アルゴリズムを導出し、ワンパスの単調スタックを実装して、その正当性と線形計算量を証明します。
コーディング面接：動的計画法で編集距離を計算するにはどうすればよいか？
文字列のプレフィックスに対する編集距離の漸化式を導出し、その3つの遷移を証明した上で、O(mn)時間およびO(min(m, n))空間のローリング配列によるTypeScript解法を実装します。
コーディング面接：最長増加部分列（LIS）をどのように求めますか？
2乗時間の動的計画法から最小末尾値の不変条件を導出し、二分探索、直前インデックス、プロパティテストを用いて、O(n log n) の最長増加部分列アルゴリズムを実装および証明します。
コーディング面接：双方向BFSでWord Ladderをどう解くか？
Word Ladderを暗黙の非重み付きグラフとしてモデル化し、最短シーケンスの契約からBFSを導出し、厳密な証明、コストモデル、および敵対的テストを用いて、より小さいフロンティアを展開する双方向探索を実装します。
コーディング面接：O(1) LFU キャッシュをどのように実装するか？
キーインデックス、頻度バケット、バケットごとの双方向連結リスト、最小頻度ポインタを用いて LFU キャッシュを実装し、get および put の期待計算量が O(1) であることを証明します。
コーディング面接：Minimum Window Substring（最小ウィンドウ部分文字列）をどう解くか？
O(N^2) の素朴な解法から可変長スライディングウィンドウを導出し、必要な文字出現頻度と条件を満たした文字種別数を追跡し、重複文字、解が存在しない入力、および全探索オラクルに対して実行可能な TypeScript 解法を検証します。
コーディング面接：2ポインタ法で雨水トラップ問題（Trapping Rain Water）を解く方法
各列の水位計算式からプレフィックス配列および2ポインタ解法を導出し、既知の境界が小さい方を安全に進められる理由を証明し、O(n) 時間・O(1) 補助空間での実装と検証を行います。
コーディング面接：k 個のソート済み連結リストをどのようにマージしますか？
フロンティア不変条件から O(N log k) のマージを導出し、サイズ k の最小ヒープで実装し、正当性を証明したうえで、線形スキャン、逐次マージ、全体ソート、分割統治法と比較します。
コーディング面接：ダイクストラ法による最短経路アルゴリズムの実装
隣接リスト、ヒープの遅延削除（lazy deletion）、および経路復元を用いてダイクストラ法を実装し、その貪欲法（greedy）の不変条件を証明した上で、早期終了、計算量、および負の重みの境界条件について解説します。
コーディング面接：Union-Find の実装と連結成分の追跡方法
動的連結性クエリから Union-Find を導出し、union by size と経路半減法（path halving）を用いて union、connected、および成分数のカウントを実装し、正当性、ならし計算量、テスト、削除の限界について解説します。
コーディング面接：単調デック（Monotonic Deque）を用いてスライディングウィンドウの最大値を解く方法
全探索やヒープによるアプローチから単調デックを導出し、支配関係・不変条件・償却解析を用いて O(n) 時間を証明した上で、真に O(k) 空間を実現する TypeScript の循環デックを実装します。
コーディング面接：二分木の最小共通祖先（LCA）を見つける
パスに基づくベースラインからワンパスの後順走査（帰りがけ順）解法を導出し、部分木の戻り値の不変条件によってそれを証明し、重複する値、存在しないターゲット、極端に深い木、および繰り返されるクエリを処理します。
コーディング面接：二分木のシリアライズとデシリアライズ
明示的な null マーカーを用いた可逆な先行順（preorder）エンコーディングを設計し、デコーダが正確に1つの部分木を消費することを証明し、不正な入力、深い木、代替フォーマットに対処します。
コーディング面接：データストリームからの中央値の取得
小さい方の半分を最大ヒープ、大きい方の半分を最小ヒープで保持し、明確な不変条件から O(log n) の挿入と O(1) のクエリを導出するとともに、正確性、エッジケース、スライディングウィンドウへの発展課題に対応します。
コーディング面接：二分探索で最初と最後の位置を特定する
下限（lower bound）と上限（upper bound）を使用して重複要素、空配列、存在しないターゲットを一貫して処理し、半開区間の不変条件（ループ不変条件）を用いて O(log n) の解法を証明します。
コーディング面接：重複する区間（Intervals）をどのようにマージするか？
ソートと貪欲法（greedy scan）を用いて重複する閉区間をマージし、端点のルール、正当性の不変条件、計算量、非破壊契約を説明した上で、包含・連鎖・ストリーミングなどの発展課題に対応します。
トポロジカルソートを用いてCourse Schedule IIを解くには？
履修前提条件からKahnのトポロジカルソートを導出し、入次数ゼロの不変条件とサイクル検出を証明し、複数の順序、重複エッジ、並列セメスターに関する発展的な質問に対処します。
Insert、Search、Prefix、Delete を備えた Trie の実装
完全一致とプレフィックスの要件から Trie を導出し、共有パスを壊さずに安全な削除を実装し、終端マーカーの不変条件、計算量、およびエッジケースを検証します。
動的な頻出上位 K 個のアイテム（Dynamic Top-K Frequent Items）向けデータ構造の設計
読み書きの比率から正確な動的 Top-K データ構造を導出し、実行可能な頻度バケットのコード、不変条件、計算量を整理した上で、制限されたメモリ環境で Space-Saving や Count-Min Sketch が必要となる条件を定義します。
スレッドセーフな有界ブロッキングキューの実装
リングバッファ、1つのロック、2つのConditionを用いて有界ブロッキングキューを実装し、状態不変条件、線形化ポイント、スプリアスウェイクアップ、および割り込みセマンティクスを通じてその正当性を証明します。