Google L3 オンサイト面接:電話面接、コーディング面接4回、行動面接1回、内定なし(シアトル、2019年)

選考プロセス

1. 電話面接

   約30分間で、二分木を分割する問題のバリエーションと、グリッド上の動的計画法の問題を扱った。面接官は、時間が足りない場合は2問目を別の問題に差し替える用意があると伝えた。

2. オンサイト日程調整

   電話面接の3日後、候補者はシアトルで1日に行われる技術面接4回と行動面接1回から成るオンサイト面接に招かれた。

3. ランチ

   現従業員との非公式なランチでは、会社に関する一般的な質問が中心で、技術的な内容は扱われなかった。

4. 結果

   内定なし。候補者は、この結果の主な要因はオンサイト最初のラウンドにあったと考えている。

電話面接

コーディング——木の再構成とグリッド上の動的計画法 · 約30分

• 与えられたノード集合を取り除いた後、二分木を森(フォレスト)に分割する問題のバリエーション。
• 二値行列の中で1のみから成る最大の正方形を見つける動的計画法の問題(最大正方形問題のバリエーション)。

通話の残り時間が約10分になった時点で、面接官は候補者がもっと時間を必要とする場合は2問目を差し替える用意があると伝えた。

オンサイト ラウンド1

コーディング——ソート済み配列に対する二分探索

• ソート済み配列が与えられたとき、あるターゲット値が出現する回数を、O(log n)時間を目標にカウントする。

候補者のアプローチは、ターゲットが見つかった後に両側を再帰的に探索するというものだったが、最悪ケース(配列全体がターゲット値で埋まっている場合)ではO(log n)を達成できなかった。振り返ると、候補者はこのラウンドが結果を左右した可能性が高いと考えている。

オンサイト ラウンド2

コーディング——追加の空間を使わない二分木の探索

• 二分木内のあるノード(ルートではない)が与えられたとき、追加の空間を使わずにその右隣のノードを見つける。
• フォローアップ:各ノードは最大深度の値(子ノードの最大深度のうち大きい方に1を加えた値)も保持している。この値を使って探索を枝刈りする。

候補者は最初、ブルートフォースの選択肢としてレベル順探索(幅優先探索)を提案したが、面接官はこれを却下した。代わりに、親ポインタと深度カウンタを使って対象ノードから上方向へたどる解法を用いた。

オンサイト ラウンド3

コーディング——トライ木を用いた単語ゲーム

• N人でプレイするマルチプレイヤーの単語ゲーム(Ghost)では、各手番で共有の文字列に1文字ずつ追加していく。追加できるのは、結果として得られる文字列が辞書内のいずれかの単語の有効な接頭辞であり、かつそれ自体が完全な単語ではない場合に限られる。合法な次の一手を決定せよ。
• フォローアップ:同じルールの下で、勝利が確定する次の文字を選べ。

有効な単語の辞書から構築したトライ木を使い、ある文字を追加した後も文字列が非終端の接頭辞のままであるかを確認した。勝利確定のフォローアップに対して候補者が提案した、終端パスと非終端パスを数え上げるアプローチは十分には成立せず、このラウンドのその部分は完全な解法に至らないまま終わった。

オンサイト ラウンド4

コーディング——施設配置のためのグリッドBFS

• 『Shortest Distance from All Buildings』のバリエーション:従業員の机、壁、空きスペースを示すオフィスのグリッドが与えられたとき、全従業員の合計歩行距離を最小にする空きスペースを見つける。
• フォローアップ:BFSベースの解法を複数スレッドに並列化するにはどうすればよいか。

解法では各従業員からBFSを実行し、共有のグリッドに距離を累積した上で、合計距離が最小となるセルを探した。

オンサイト ラウンド5——行動面接

行動面接

• プロジェクトの方向性に不満を感じた経験について話してください。
• これまでに取り組んだ中で、技術的に最も難しかったことは何ですか。
• あなたのキャリアの目標は何ですか。またそれを達成するための計画は。
• チームと意見が対立した経験について話してください。
• チームを助けるために期待以上のことをした経験について話してください。