Baidu 面接質問

Baidu 面接の重点項目

Baidu のよくある面接質問

• 整数の配列が与えられたとき、最長の増加部分列を見つけてください。
  良い回答が押さえる点

  • 動的計画法（DP）を用いる場合、O(n^2)の時間計算量で各部分列の長さを記録する。
  • より効率的な方法として、二分探索を用いたO(n log n)のアルゴリズム（パターンスソーティング）がある。
  • 実際の部分列を再構築するには、前の要素のインデックスを保持する配列が必要。
  • 配列が空の場合のエッジケースに注意する。

  サンプル回答を見る

  最長増加部分列（LIS）問題は、与えられた数列から部分列を選び、各要素が前の要素より大きいという条件を満たす最長の長さを求める。動的計画法では、dp[i]をi番目で終わるLISの長さとし、すべてのj<iでarr[j] < arr[i]ならdp[i] = max(dp[i], dp[j]+1)と更新する。時間計算量はO(n^2)。より高速な方法として、tails配列を用意し、tails[l]を長さl+1のLISの最後の最小値とする。各要素xに対して二分探索でxを挿入する位置を見つけ、tails[pos] = xと更新する。最終的な長さはtailsの長さとなる。この方法はO(n log n)で動作する。部分列そのものを得るには、各要素の前のインデックスを記録しておく。

  def lengthOfLIS(nums):
      import bisect
      tails = []
      for num in nums:
          pos = bisect.bisect_left(tails, num)
          if pos == len(tails):
              tails.append(num)
          else:
              tails[pos] = num
      return len(tails)
  
  # 使用例
  nums = [10, 9, 2, 5, 3, 7, 101, 18]
  print(lengthOfLIS(nums))  # 出力: 4 (2,5,7,101)
  
  # 時間計算量: O(n log n), 空間計算量: O(n)

• 有向グラフの循環を検出する関数を実装してください。
  良い回答が押さえる点

  • DFSを用いて各ノードの状態（未訪問、訪問中、訪問済み）を管理する。
  • バックエッジ（訪問中のノードへのエッジ）が存在すれば循環がある。
  • トポロジカルソート（Kahnのアルゴリズム）でも検出可能で、キューを用いて次数が0のノードを処理する。
  • グラフが連結でない場合も考慮する必要がある。

  サンプル回答を見る

  有向グラフの循環検出には、DFSを使った三色法が一般的である。各ノードに0（未訪問）、1（訪問中）、2（訪問済み）の状態を割り当てる。DFSでノードを探索する際、そのノードを訪問中（1）に設定し、隣接ノードを再帰的に訪れる。もし隣接ノードがすでに訪問中であれば、循環が存在する。すべての隣接ノードの探索が終わったら、状態を訪問済み（2）に更新する。また、Kahnのアルゴリズムでは、入次数が0のノードから順に処理し、処理済みノード数が総ノード数と一致しなければ循環がある。どちらの方法も時間計算量はO(V+E)である。

  def hasCycle(graph):
      # graph: dict of adjacency list, nodes: 0..n-1
      state = [0] * len(graph)  # 0: unvisited, 1: visiting, 2: visited
  
      def dfs(v):
          if state[v] == 1:
              return True  # 循環発見
          if state[v] == 2:
              return False
          state[v] = 1
          for neighbor in graph[v]:
              if dfs(neighbor):
                  return True
          state[v] = 2
          return False
  
      for v in range(len(graph)):
          if state[v] == 0:
              if dfs(v):
                  return True
      return False
  
  # 使用例
  graph = {
      0: [1, 2],
      1: [2],
      2: [3],
      3: [1]  # 循環: 1->2->3->1
  }
  print(hasCycle(graph))  # True
  
  # 時間計算量: O(V+E), 空間計算量: O(V)

• Baiduのようなリアルタイム検索オートコンプリートシステムを設計してください。
  良い回答が押さえる点

  • オートコンプリートではTrie（プレフィックスツリー）が基本的なデータ構造。
  • リアルタイム性を確保するため、各ノードで頻度ランキングを保持し、トップk候補を返す。
  • 更新クエリ（新しい検索語）は非同期で処理し、キャッシュを利用して負荷を軽減。
  • 分散環境では、Trieをシャーディングし、各ノードが異なるプレフィックスを担当する。
  • 冗長性と可用性のためにレプリケーションとコンセンサスアルゴリズム（Raftなど）を使用。

  サンプル回答を見る

  Baiduのようなリアルタイム検索オートコンプリートシステムを設計するには、まずユーザーが入力するたびに候補を返す必要があるため、高速なデータ構造が求められる。中核となるのはTrieで、各ノードにはそのプレフィックスを持つ検索語とその頻度を保持する。ユーザーの入力に応じてTrieを走査し、頻度の高いトップk（例えば10件）の候補を返す。リアルタイム性を高めるため、頻度のランキングは各ノードに事前計算して保持するか、またはヒープを用いて動的に取得する。検索語の追加や頻度更新は非同期に行い、書き込み負荷を分離するためにメッセージキュー（Kafkaなど）を使う。キャッシュ層（Redisなど）を導入してホットなプレフィックスを高速に応答する。データ量が膨大になるため、Trieを複数のサーバーにシャーディングする。例えば、プレフィックスのハッシュ値や文字範囲で分割し、各サーバーは担当範囲のTrieを保持する。さらに、可用性のために各シャードをレプリケーションし、ZooKeeperなどでクラスタ管理を行う。障害時に迅速にフェイルオーバーできるようにする。また、CDNやエッジサーバーを活用して地理的に分散したユーザーに低レイテンシを提供する。プライバシーやキャッシュの一貫性にも注意が必要である。

• 高トラフィックのウェブサイト向けの分散キャッシュを設計してください。
  良い回答が押さえる点

  • 分散キャッシュにはコンシステントハッシュを用いてノードの追加・削除時の再配置を最小化。
  • キャッシュエビクションポリシーはLRUやLFUが一般的だが、用途に応じて選択。
  • データのレプリケーションにより可用性を高め、各ノードが複製を持つ。
  • CDNを併用し、静的コンテンツはCDNにキャッシュさせる。
  • 書き込み時にはキャッシュとデータベースの一貫性を保つためにライトスルーやライトビハインド戦略を採用。

  サンプル回答を見る

  高トラフィックウェブサイト向けの分散キャッシュシステムを設計する際、まずスケーラビリティと可用性が重要である。キャッシュデータの分散にはコンシステントハッシュを使用する。これにより、ノードの追加や削除が発生しても、再配置されるキーの範囲が限定され、影響が少ない。各キャッシュノードはメモリ上にデータを保持し、エビクションポリシーとしてLRU（Least Recently Used）を採用するのが一般的だが、アクセスパターンによってはLFUも検討する。可用性向上のために、各データを複数のノードにレプリケーションする。例えば、コンシステントハッシュのリング上で後続のノードにレプリカを配置する。クライアントは読み取り時にプライマリノードかレプリカからデータを取得する。書き込み時はプライマリに書き込み、非同期でレプリカに反映する。また、CDNを導入して静的コンテンツや画像をキャッシュし、オリジンサーバーの負荷を軽減する。キャッシュとデータベースの一貫性を保つために、ライトスルー戦略（キャッシュとDBに同時書き込み）またはライトビハインド（非同期でDBに書き込み）を選択する。なお、キャッシュミス時のスパイクを防ぐため、キャッシュウォーミングやサーキットブレーカーを実装する。監視とログ分析により、ホットキーを特定してプリフェッチすることも有効である。

• L1とL2正則化の違いと、それぞれをいつ使用するかを説明してください。
  良い回答が押さえる点

  • L1正則化（Lasso）はパラメータの絶対値にペナルティをかけ、スパースな解を促進する。
  • L2正則化（Ridge）はパラメータの二乗にペナルティをかけ、過学習を防ぎつつ係数を縮小する。
  • L1は特徴選択に役立ち、解釈性が求められる場合に適している。
  • L2はすべての特徴を少しずつ使いたい場合や、特徴間に相関がある場合に有効。
  • 収束性: L1は微分不可能な点があるため、最適化がやや難しい。

  サンプル回答を見る

  L1正則化とL2正則化は、モデルの過学習を防ぎ、汎化性能を向上させるための手法である。L1正則化（Lasso）は損失関数にパラメータの絶対値の和（L1ノルム）を加える。その結果、多くのパラメータが正確にゼロになり、スパースなモデルが得られる。これは特徴選択の効果があり、高次元データで不要な特徴を排除したい場合や、モデルの解釈性が重要な場合に適している。一方、L2正則化（Ridge）はパラメータの二乗和（L2ノルム）を加える。これによりパラメータはゼロに近づくが完全にはゼロにならず、すべての特徴をある程度保持しながら係数を縮小する。L2は特徴間に多重共線性がある場合や、すべての特徴が重要である可能性がある場合に有効である。また、L2の方が微分可能であるため、最適化が容易で収束が速い。実際のタスクによっては、両方の正則化を組み合わせたElastic Netも使用される。選択基準として、特徴数がサンプル数より多い場合はL1が効果的であり、そうでない場合はL2が安定することが多い。

• 分類問題におけるクラス不均衡にどのように対処しますか？
  良い回答が押さえる点

  • クラス不均衡は、多数派クラスに偏ったモデル学習を引き起こす問題。
  • アンダーサンプリング：多数派クラスからランダムに削除するが、情報損失のリスク。
  • オーバーサンプリング：少数派クラスを複製するが、過学習のリスク。SMOTEは合成データ生成。
  • アルゴリズムレベル：クラス重みを設定し、少数派の誤分類ペナルティを大きくする。
  • 評価指標として適合率・再現率・F1スコアやAUC-ROCを使用し、精度は避ける。

  サンプル回答を見る

  分類問題におけるクラス不均衡は、一方のクラスのサンプル数が他方を著しく上回る状況で、モデルが多数派クラスに偏って学習される問題を引き起こす。対処法はデータレベルとアルゴリズムレベルの二つに大別される。データレベルでは、多数派クラスのサンプルを減らすアンダーサンプリングと、少数派クラスを増やすオーバーサンプリングがある。アンダーサンプリングは計算効率が良いが情報損失の恐れがある。オーバーサンプリングは単純複製では過学習になりやすいため、SMOTE（Synthetic Minority Over-sampling Technique）を用いて少数派クラスの近傍から合成データを生成するのが効果的。アルゴリズムレベルでは、損失関数にクラス重みを導入し、少数派クラスの誤分類に対するペナルティを大きくする方法がある。例えば、sklearnのclass_weight='balanced'を使用する。また、異常検知として扱い、少数派を異常値とみなす手法もある。評価指標は精度ではなく、適合率、再現率、F1スコア、またはAUC-ROCを使用すべきである。不均衡が極端な場合は、pr曲線のAUCも検討する。さらに、アンサンブル学習（EasyEnsemble、BalanceCascadeなど）や、コスト考慮型学習も有効である。

• 厳しい締め切りの下でプロジェクトを納品しなければならなかった経験について教えてください。
  良い回答が押さえる点

  • 状況：前職での大規模なデータ移行プロジェクト。
  • タスク：3ヶ月の計画を1ヶ月に短縮する必要があった。
  • 行動：タスクを優先順位付けし、コア機能に集中、チームを分割し並行作業、毎日の進捗確認。
  • 結果：期限内に納品し、品質も維持。顧客から高い評価を得た。

  サンプル回答を見る

  以前、私は大手金融機関でデータ移行プロジェクトを担当していました。当初3ヶ月の計画でしたが、顧客の要件変更により納期が1ヶ月に短縮されました。私はまずプロジェクトのスコープを見直し、必須機能とオプション機能を明確にしました。そして、チームを3つのサブチームに分割し、並行して作業できるようにしました。各サブチームには明確な目標を設定し、毎日15分のスタンドアップミーティングで進捗を共有しました。また、リスクが高いタスクには追加のテスト時間を割り当てました。結果として、期日通りにシステムを納品し、データの整合性も保たれました。プロジェクト終了後、顧客からは「非常にプロフェッショナルだった」と評価され、チームの士気も向上しました。この経験から、厳しい締め切り下では明確な優先順位付けと効果的なコミュニケーションが不可欠だと学びました。

• チームメンバーと意見が合わなかった状況と、どのように解決したかを説明してください。
  良い回答が押さえる点

  • 状況：機械学習モデルの特徴量選択手法について意見が分かれた。
  • タスク：チームメンバーがラッパー法を推す一方、私はフィルター法を主張。
  • 行動：両手法の利点を比較検討し、小規模な実験を提案。
  • 結果：実験の結果、フィルター法が計算効率と性能のバランスで優れていると結論、合意に至った。

  サンプル回答を見る

  以前、チームで機械学習モデルの特徴量選択手法を決める際、一人のメンバーが計算コストが高いが精度の高いラッパー法を推し、私はより高速でスケーラブルなフィルター法を主張しました。議論は平行線をたどりましたが、私は対立を解消するために、両手法を小規模なサブセットで比較実験することを提案しました。実験では、同じデータセットで各手法を適用し、モデル性能と実行時間を測定しました。結果、フィルター法はラッパー法とほぼ同等の精度を達成し、実行時間は大幅に短縮されました。このデータに基づき、チームはフィルター法を採用することで合意しました。この経験から、意見の相違は建設的な議論につながること、そして客観的な証拠を示すことで効果的に解決できることを学びました。

準備のヒント

• 動的計画法、木、グラフに焦点を当ててデータ構造とアルゴリズムをマスターしましょう。これらはBaiduの面接でよく出ます。
• 分散システムのシステムデザインを練習し、特に検索、レコメンデーション、大規模データ処理の文脈で練習しましょう。
• 教師あり学習と教師なし学習、オーバーフィッティング、特徴選択、モデル評価指標など、MLの核となる概念を復習しましょう。
• 自分の思考プロセスを明確に説明し、ホワイトボードまたは共有エディタでバグのないコードを書く準備をしましょう。
• Baiduの製品（Baidu Search、Apollo、DuerOSなど）を調査して、彼らが直面している技術的課題を理解しましょう。

よくある質問