面接質問と回答の解説 — ページ 50 / 52
Offer.ccの面接質問と回答解説の50ページ目を閲覧。思考プロセス、実装の詳細、深掘り質問、公開情報ソースを確認できます。
コーディング面接：長さが未知のストリームから一様にサンプリングするにはどうすればよいか？
リザーバーサンプリングを使用して、O(k) のメモリと1パスで等確率な k 個の要素を維持し、不変条件を証明して境界条件を処理します。
分散型ユニークIDジェネレータをどのように設計しますか？
キャパシティ制約からSnowflakeのビットレイアウトを導出し、クロックロールバック、ワーカーアイデンティティ、シーケンス枯渇、マルチリージョン障害に対処した上で、UUIDv7やセグメント割り当てと比較します。
不均衡データにおける分類器の評価
混同行列、審査処理能力、およびエラーコストから分類指標と決定閾値を導出し、AUROC、適合率・再現率、キャリブレーション、およびベースレート監視のそれぞれの役割を解説します。
コーディング面接：重複しないジョブで報酬を最大化するには？
重み付き区間スケジューリングを用いてソート、二分探索、動的計画法を結び付け、正確な境界、証明、計算量、経路復元を解説します。
分散ジョブスケジューラをどのように設計しますか？
オカレンス識別子、シャーディングされた時間インデックス、および At-least-once 配信を使用して、単発ジョブおよび cron ジョブ向けのマルチテナントスケジューラを設計し、同期ピーク、ミスクライ、タイムゾーン、キャンセルの競合、およびリカバリを処理します。
機械学習におけるデータリーク（情報漏洩）の検知と防止
不正検知モデルを例に、予測時点のコントラクトを定義し、ターゲットリーク、時間的リーク、エンティティリーク、前処理リークを調査した上で、信頼性の高いデータ分割、交差検証、最終ホールドアウト評価を構築します。
コーディング面接：動的配列の実装とならしO(1)のappendの証明方法
容量の不変条件、幾何学的増加、ならし解析の証明を用いてインデックス参照可能な動的配列を実装し、空間コストおよび最悪ケースのコストを解説します。
マルチチャネル通知システムの設計
面接の前提として1日あたり10億件のチャネル配信タスクを想定し、優先度分離、正確な配信状態、順不同のコールバック、リトライ、検証可能なリカバリを備えた、OTPとマーケティングキャンペーンの双方に対応する通知システムを設計します。
ストリーム処理における遅延イベントおよび順序不同イベントの処理
イベント時間、ウォーターマーク、許容される遅延（allowed lateness）、重複排除状態を用いて時間別売上を導出するストリーム処理設計を行い、補正、状態クリーンアップ、障害復旧、オフライン照合までをカバーします。
コーディング面接：最も頻出するK個の単語をどのように返しますか？
頻度カウント、カスタム最小ヒープ、および正確な頻度／辞書順コンパレータを使用して、O(n log k) の時間で頻出上位K個の単語を返します。
システムデザイン面接：複数リージョンにまたがるグローバルレート制限の適用
グローバルなAPI制限のためのクォータリースの設計、ネットワーク分断時の超過量（オーバーシュート）の定量化、トラフィックが集中するホットリージョンのリバランス、および明確なフェイルオープン／フェイルクローズ動作の選択について解説します。
コーディング面接：重複を拒否するカレンダーをどのように実装するか？
半開区間、先行要素・後続要素の検索、および順序付きマップを使用して、明確な境界と計算量で My Calendar I を解決します。
コーディング面接: 壊れた2つのヒープによるストリーミング中央値のデバッグ
ヒープの順序、サイズ、空状態、およびオーバーフローに関する不変条件を復元することで、敵対的な挿入後に誤った値を返す MedianFinder を診断します。
コーディング面接：O(1) の Min Stack（最小値を取得できるスタック）をどのように実装しますか？
push、pop、top、getMin を O(1) で実行できるよう、重複する最小値や空スタック時の挙動も含めてプレフィックス最小値スタックを保持します。
コーディング面接：Bloom Filterの実装
Bloom FilterのaddおよびmightContainを実装し、偽陽性、サイジング、削除の制約、テストについて解説します。
コーディング面接：スレッドセーフな読み書きロック（Read-Write Lock）の実装
ミューテックスと条件変数を使用して読み書きロックを実装し、公平性、アップグレード、および障害ケースについて考察します。
コーディング面接：有効期限付きTTLキャッシュの実装
ハッシュテーブル、有効期限タイムスタンプ、クリーンアップ、および並行性ルールを使用して、テスト可能なTTLキャッシュを実装します。
コーディング面接：マージとクエリを備えた区間セットをどのように実装しますか？
境界条件と計算量の考察を含め、追加、削除、点検索、および範囲重複クエリを備えた非重複区間の正規化セットを実装します。
コーディング面接：更新と削除を備えた可変優先度付きキューをどう実装するか？
ヒープ、インデックスマップ、遅延削除（lazy deletion）を使用して更新可能な優先度付きキューを実装し、安定した同順位タイの解決、削除、古いエントリ、計算量の証明まで網羅します。
コーディング面接：再開可能なバッチイテレータをどのように設計するか？
hasNext/next の規約から始め、リモートページを読み込み、安全に再開し、重複を回避し、障害を伝播するイテレータを設計します。
コーディング面接：スナップショット配列の実装（Snapshot Array）
インデックスごとの変更履歴、書き込みの結合、先行要素（predecessor）の二分探索を用いたバージョン管理配列を設計し、時間計算量、空間計算量、スナップショットのセマンティクスを証明します。
コーディング面接：必要な会議室の最小数
会議の区間を並行リソース使用量に変換し、2つの配列を用いた走査線法で最小の会議室数を計算して、半開区間の端点、同時発生イベント、ヒープによる代替案、および部屋割り当ての発展課題を含めて重複の深さから最適性を証明します。
コーディング面接：トポロジカルソートでエイリアン辞書（Alien Dictionary）を解く
ソート済み単語リストから正当な優先順位エッジのみを抽出して未知のアルファベットを推論します。面接で完全な回答を行うための無効な接頭辞ルール、閉路検出、正当性の証明、曖昧性チェック、および敵対的テストを学びます。
コーディング面接：反復型DFSによる島（Islands）の数のカウント
連結成分のモデル化からインプレースな反復型DFSを導出し、プッシュ時にセルを訪問済みにマークすべき理由を解説した上で、正当性、計算量、境界テスト、代替手法まで網羅します。