Google 面接質問

Google 面接の重点項目

Google のよくある面接質問

• 整数の配列が与えられたとき、合計が特定のターゲットになる2つの数のインデックスを返してください。(古典的なtwo-sum問題ですが、複数の解法を求め、計算量について議論します。)
  良い回答が押さえる点

  • ブルートフォース O(n^2)
  • ハッシュマップ O(n), 空間 O(n)
  • ソート + 双方向走査 O(n log n)
  • 重複と順序の考慮

  サンプル回答を見る

  Two-Sum問題では、まずブルートフォースで二重ループを用いるとO(n^2)の時間がかかりますが、これは非効率です。最適な解法はハッシュマップを使用することで、各要素を走査しながら、ターゲットとの差がすでにマップに存在するかを確認します。これにより時間計算量O(n)、空間計算量O(n)で解けます。また、ソートしてから双方向ポインタを使う方法もありますが、その場合はO(n log n)の時間がかかります。注意点として、同じ要素を二度使えないことと、インデックスを返す必要があるため、ハッシュマップには値とインデックスを保存します。フォローアップとして、ソート済み配列であれば双方向ポインタでO(n)かつO(1)空間で解けることを説明できると良いでしょう。

  def two_sum(nums, target):
      seen = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              return [seen[complement], i]
          seen[num] = i
      return []

• bit.lyのようなURL短縮サービスを設計してください。データベーススキーマ、ハッシュ、スケーリング、リダイレクトの処理について議論します。
  良い回答が押さえる点

  • ハッシュ関数 (Base62, ランダム)
  • データベーススキーマ (id, original_url, short_key, created_at)
  • リダイレクト (301 vs 302)
  • スケーリング (キャッシュ, シャーディング, コンシステントハッシュ)

  サンプル回答を見る

  URL短縮サービスでは、まず要件として短いユニークなキーを生成する必要があります。ハッシュ関数はBase62エンコードやランダム文字列生成が一般的で、衝突を避けるために重複チェックが必要です。データベーススキーマは、id（整数）、original_url（文字列）、short_key（ユニークインデックス）、created_atなどのカラムを持ちます。リダイレクトには301（恒久的）と302（一時的）があり、統計情報を取得したい場合は302を使用して毎回アクセスを記録します。スケーリングでは、短いキーへのアクセスは非常に多いため、Redisなどのキャッシュ層を導入します。データベースのシャーディングにはshort_keyをハッシュベースで分散させるコンシステントハッシュを用いると、ノード追加時の再配置を最小限に抑えられます。また、短いキーの生成を一意に保つために、IDジェネレータ（例：Snowflake）を別途用意することも検討します。

• 同僚との衝突があった時のことを教えてください。どのように解決しましたか？(行動面接 – 協力と結果に焦点を当てます。)
  良い回答が押さえる点

  • 状況: プロジェクトの方向性で意見対立
  • タスク: チームとして最適解を導く
  • 行動: データに基づく議論, 妥協案, エスカレーション回避
  • 結果: 合意とプロジェクト成功

  サンプル回答を見る

  以前のプロジェクトで、新機能の実装方法について同僚と意見が対立しました。彼は迅速にリリースしてユーザーフィードバックを得ることを優先し、私はコードの保守性とテストカバレッジを重視していました。まず、互いの懸念を理解するために1対1のミーティングを設定し、それぞれのメリットをデータで示しました。例えば、彼の提案は市場投入までの時間を短縮できる一方、技術負債が蓄積するリスクがあることを具体的な事例で説明しました。最終的に、MVPとして最小限の実装でリリースし、その後リファクタリングを行う段階的アプローチで合意しました。この妥協により、チームは迅速にリリースしつつ、品質も維持でき、プロジェクトは成功裏に完了しました。この経験から、意見の相違は建設的な議論を通じてチームの成長につなげられることを学びました。

• 二分木の直列化および復号化を行う関数を実装してください。(nullの処理、再帰、反復のテスト。)
  良い回答が押さえる点

  • 直列化: 先行順巡回, nullを'#'で表現
  • 復号化: キューを使用した再帰的構築
  • 時間 O(n), 空間 O(n)
  • エッジケース: 空の木, 片方だけ子がある場合

  サンプル回答を見る

  二分木の直列化では、木を文字列に変換し、復号化で元の木を再構築します。よく使われる方法は先行順巡回（preorder）で、nullの場合は特別なマーカー（例：'#'）を挿入します。直列化の時間計算量はO(n)で、各ノードを一度訪問します。復号化では、直列化された文字列をカンマなどで分割し、リストまたはキューに格納します。再帰関数で先頭から値を取り出し、'#'ならnullを返し、それ以外はノードを生成して左右の子を再帰的に構築します。これもO(n)です。注意点として、カンマなどの区切り文字を適切に扱い、数値が複数桁の場合にも対応する必要があります。エッジケースとして、空の木（空文字列）や、片方だけ子がある場合のテストが重要です。反復的な方法も存在しますが、再帰がシンプルで自然です。

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  def serialize(root):
      def dfs(node):
          if node is None:
              return '#'
          return str(node.val) + ',' + dfs(node.left) + ',' + dfs(node.right)
      return dfs(root)
  
  def deserialize(data):
      def dfs(queue):
          val = queue.popleft()
          if val == '#':
              return None
          node = TreeNode(int(val))
          node.left = dfs(queue)
          node.right = dfs(queue)
          return node
      from collections import deque
      q = deque(data.split(','))
      return dfs(q)

• Googleマップのリアルタイム交通情報機能を設計してください。データ収集、ルート更新、数百万ユーザーの処理をどのように行いますか？
  良い回答が押さえる点

  • データ収集: GPS, 携帯電話, センサー, パートナーからのデータ
  • ルート更新: グラフ構造とトラフィックレイヤー, ダイクストラ法
  • スケーリング: 分散処理 (MapReduce, ストリーム処理), キャッシング
  • リアルタイム性: パブサブシステム, 更新頻度の調整

  サンプル回答を見る

  Googleマップのリアルタイム交通情報は、まずデータ収集が重要です。携帯電話のGPSデータ、道路センサー、政府機関、Wazeなどのプローブデータを収集します。これらは膨大なストリームデータなので、Apache KafkaやPub/Subシステムで処理し、リアルタイムに集計します。ルーティングには、道路ネットワークをグラフとして持ち、各エッジに現在の速度、遅延などの重みを動的に割り当てます。ルート計算にはダイクストラ法やA*アルゴリズムを使用しますが、全ユーザーに対して毎回計算するのは負荷が高いため、部分的なプリ計算やキャッシュを活用します。スケーリングでは、地理的領域ごとにサーバーを分割し、データ処理にはMapReduceやストリーム処理エンジン（例：Apache Flink）を用います。ユーザーへの配信は、変化があった部分のみを更新することで帯域を節約します。ボトルネックはイベント処理のレイテンシとデータベースの書き込み負荷であるため、タイムウィンドウ集計とメモリ内キャッシュ（例：Redis）で対処します。

• 最も誇りに思うプロジェクトについて説明してください。あなたの役割、課題、影響は何でしたか？(行動面接 – 主体性と影響力を評価します。)
  良い回答が押さえる点

  • 状況: 大規模なデータ移行プロジェクト
  • 役割: テクニカルリーダー, アーキテクチャ設計
  • 課題: ダウンタイムゼロ, データ整合性
  • 影響: 移行成功, パフォーマンス改善50%
  • 学び: チーム調整と段階的ロールアウトの重要性

  サンプル回答を見る

  最も誇りに思うプロジェクトは、前職での大規模なデータ移行プロジェクトです。私はテクニカルリーダーとして、レガシーシステムから新しいマイクロサービスアーキテクチャへのデータ移行を設計・実装しました。最大の課題は、ダウンタイムゼロでデータの整合性を保ちながら移行することでした。私は段階的な移行戦略を提案し、まず読み取り専用のシャドウシステムを構築してデータを同期し、差分を検証しました。その後、ダブルライト方式で書き込みも徐々に新しいシステムに切り替え、最終的に旧システムを廃止しました。このプロジェクトにより、クエリのレイテンシが50%改善し、システムの拡張性が大幅に向上しました。チームメンバーとの密なコミュニケーションと、段階的ロールアウトの重要性を学び、自信となりました。

• 整数のストリームが与えられたとき、任意の時点で中央値を見つけてください。(2つのヒープ – 最大ヒープと最小ヒープを使用します。)
  良い回答が押さえる点

  • 2つのヒープ: 最大ヒープ (下半分) + 最小ヒープ (上半分)
  • 挿入 O(log n), 中央値取得 O(1)
  • バランス条件: サイズ差1以内
  • エッジケース: ストリームが空の場合

  サンプル回答を見る

  整数のストリームから中央値を求めるには、2つのヒープを使用する方法が一般的です。最大ヒープ（lower）は下半分の最大値を保持し、最小ヒープ（upper）は上半分の最小値を保持します。新しい数値が来たら、まずlowerに挿入し、その後lowerの最大値をupperに移動してバランスを取ります。さらに、upperのサイズがlowerより大きい場合は、upperの最小値をlowerに移動します。これにより、常にlowerとupperのサイズ差が1以下になります。中央値は、サイズが等しい場合は(lowerの最大値 + upperの最小値)/2、そうでなければ大きい方のヒープのトップになります。時間計算量は挿入ごとにO(log n)、中央値取得はO(1)です。注意点として、値が重複する場合の扱いと、ストリームが空の場合の例外処理が必要です。この方法は、データ数が増えても効率的に中央値を追跡できるため、リアルタイムシステムに適しています。

  import heapq
  
  class MedianFinder:
      def __init__(self):
          self.lower = []  # max heap (negative values)
          self.upper = []  # min heap
  
      def addNum(self, num: int) -> None:
          heapq.heappush(self.lower, -num)  # 最大ヒープのため負数
          # バランス: lowerの最大をupperへ
          heapq.heappush(self.upper, -heapq.heappop(self.lower))
          # サイズ調整: upperが大きくなりすぎたら戻す
          if len(self.upper) > len(self.lower):
              heapq.heappush(self.lower, -heapq.heappop(self.upper))
  
      def findMedian(self) -> float:
          if len(self.lower) == len(self.upper):
              return (-self.lower[0] + self.upper[0]) / 2.0
          else:
              return -self.lower[0]

• なぜGoogleを志望しますか？あなたが当社の文化に適している理由は何ですか？(行動面接 – 個人の価値観をGoogleのミッションに関連付けます。)
  良い回答が押さえる点

  • Googleのミッション: 情報を整理し、世界中の人々がアクセスできるようにする
  • 自分の価値観: スケールとインパクトへの情熱
  • 具体例: オープンソースへの貢献, 大規模システムの経験
  • 文化適合: コラボレーション, 失敗から学ぶ姿勢

  サンプル回答を見る

  Googleを志望する理由は、同社のミッション「世界中の情報を整理し、世界中の人々がアクセス可能で役立つものにすること」に強く共感するからです。私はこれまで、大規模なデータ処理システムの構築やオープンソースプロジェクトへの貢献を通じて、テクノロジーで社会にインパクトを与えることに情熱を注いできました。Googleはそのスケールと、革新的な問題に取り組む文化において、自分のスキルを最大限に活かせる環境だと感じています。また、Googleの「失敗から学ぶ」文化や「コラボレーション」を重視する姿勢は、私がこれまでのキャリアで培ってきた価値観と一致します。例えば、前職ではクロスファンクショナルチームと協力して困難なプロジェクトを達成し、失敗から素早く学ぶことで改善を重ねてきました。私はGoogleの一員として、大規模な課題に挑戦し、ユーザーに直接価値を提供できる仕事をしたいと考えています。

準備のヒント

• ホワイトボードやIDEなしでコーディングを練習してください：Googleの面接では手書きでコードを書くことが多いので、平らな場所で考えて書くことに慣れてください。
• 常に声に出して考えてください：面接官はあなたの問題解決プロセスを見たいので、アプローチ、トレードオフ、デバッグの手順を説明してください。
• コアデータ構造をマスターしてください：配列、文字列、木、グラフ、ハッシュテーブルに焦点を当ててください。これらはほとんどのコーディング問題に出てきます。時間計算量と空間計算量について議論できる準備をしてください。
• スケーラビリティを学んでシステムデザインに備えてください：キャッシング、ロードバランシング、シャーディング、CAP定理を理解してください。YouTube、Twitter、チャットサービスなどのシステム設計を練習してください。
• STARメソッドで行動のストーリーを見直してください：状況、課題、行動、結果を中心に回答を構成し、Googleのリーダーシップ原則（例：「骨太であれ、異議を唱えてもコミットせよ」）に合わせて調整してください。

よくある質問