Google SDE 1 オンサイト面接体験談:単語変換の到達可能性問題とタイピング距離問題

選考プロセス

1. 背景

   候補者は最近MicrosoftとGoogle両方の面接を受け、両方の体験を一緒にまとめて書いていた。Googleについては、オンサイトの技術面接のみが詳細に記述されている。

2. オンサイト ラウンド1

   与えられた辞書内の単語間の到達可能性を中心とした単一の問題で、1回の遷移で1文字を追加または削除する。

3. オンサイト ラウンド2

   1セッションで2つの独立した問題が出題された:グリッド上でのタイピング距離最適化問題と、集合の外れ値検出問題。

4. 結果

   投稿ではGoogleの選考の最終決定については述べられていない。同じ体験談の中で候補者が確定したオファーは、Googleではなく別のMicrosoftの面接ループによるものだった。

オンサイト技術面接 ラウンド1

単語変換における到達可能性(グラフ/BFS的な思考)

• 単語の辞書が与えられたとき、開始単語から終了単語まで到達できるかどうかを判定せよ。ただし、経路上のすべての中間単語も辞書に存在している必要があり、1回の遷移では単語中の任意の位置に1文字を追加するか、任意の位置から1文字を削除するかのいずれかを行う。

候補者は、短い開始単語からより長い終了単語への有効な連鎖を示す小さな例の辞書を使ってこの考え方を説明した。

オンサイト技術面接 ラウンド2

2つの独立した問題:キーボード距離の最適化と集合の外れ値検出

• 小さなグリッド(9文字、9文字、8文字の3行)に順番に並んだ文字と、対象の文字列が与えられたとき、2本の指を使って文字列のすべての文字を入力するために必要な指の総移動距離の最小値を求めよ。両方の指は任意の位置からスタートしてよく、目標は総移動量を最小化することである。
• 文字の集合の配列が与えられたとき、組み込みの集合積(intersection)メソッドを使わずに、配列内の他のどの集合とも重ならない最長の集合を求めよ。

候補者は、タイピング距離の問題が既知の「2本指タイピング距離」問題に似ていると述べ、外れ値集合の問題についてはライブラリ呼び出しではなく手動での積集合チェックが必要だと指摘した。