Google バックエンドエンジニア面接体験談:バンガロール・オンサイト(不採用)

選考プロセス

1. リクルーター電話面接

   リクルーターが短い通話を行い、基本的なアルゴリズムの計算量や概算に関する質問をした後、候補者を技術面接へと進めた。

2. 勝ち抜き選考ラウンド

   候補者が「勝ち抜き選考ラウンド」と表現した単発の技術面接では、木の走査問題が出題され、これに通過することでオンサイトループへの進出資格が得られた。

3. オンサイトまでの準備期間

   勝ち抜き選考ラウンドからオンサイトループまでは約3週間の間隔があり、候補者はこの期間を準備に充てた。

4. オンサイトループ

   オンサイトは、トライ木/DFSによる文字列問題、優先度付きキューによるスケジューリング問題、グラフ/Union-Find問題を扱う、休憩なしで連続する3回の技術面接から構成されていた。

5. 結果連絡

   3回のオンサイトラウンドの結果が芳しくない部分もあったことを受け、翌日にリクルーターから電話があり、チームとして選考を進めないことが伝えられた。

リクルーター電話面接

基本的なアルゴリズムの計算量と簡単な概算(エンジニアではなくリクルーターが担当)

• マージソートの時間計算量は、最良・平均・最悪の各ケースでそれぞれどうなるか。
• 最短経路を求めるためにBFSを使うのはどのような場合か、また、それはどのようなグラフに当てはまるか。
• 電卓を使わずに2の22乗を概算せよ。

勝ち抜き選考ラウンド(技術電話面接)

独自のスコアリングルールを伴う木の走査

• 二分木が与えられたとき、上のノードから下のノードへと向かう、等差数列をなす最長のパスの長さを求めよ。
• 追加質問:同じ考え方を、上から下への二分木の階層構造ではなく、横方向に分岐するn分木に適用する場合、アプローチはどう変わるか。

候補者は主問題をBFSベースのアプローチで解いた。

オンサイト第1ラウンド

文字列集合に対するトライ木とDFS

• 単語の集合が与えられたとき、各単語が直前の単語にちょうど1文字を追加したものになっている最長の系列を求めよ(LeetCodeのLongest String Chainに似たパターン)。

候補者はトライ木と深さ優先探索を組み合わせて解いたが、エッジケースを一つ見落としており、コードの品質・効率・ペース配分のいずれも改善が必要だと指摘された。

オンサイト第2ラウンド

優先度付きキューを用いた貪欲法によるスケジューリング

• [jobId, startTime, duration]の形でジョブが与えられたとき、実行可能なジョブの中から常に所要時間が最短のものをキューから選んで処理する、単一プロセッサを設計せよ。
• 追加質問:プロセッサが1台ではなく2台になった場合、設計はどう変わるか。

候補者は優先度付きキューとタイマーを用いて約15分でコアとなる解法を完成させ、さらにタイマーを追加することで2プロセッサ対応に拡張した。このラウンドについてのフィードバックは好意的だった。

オンサイト第3ラウンド

グラフの連結性/Union-Find

• 候補者が後にLeetCode 947番、Most Stones Removed with Same Row or Columnと同一だと特定した問題。

候補者はこの問題を見たことがなかったが、5〜10分以内に正しいアプローチを説明した。しかしコーディングの途中で行き詰まり、時間切れとなった。