2007/08/28

Google Interview (電話面接その3)

先週の終わりに3回目の電話面接を受けました。2回目の電話面接から約3週間経っていました。この間、Googleなんて忘れて、ちょっとゆっくり家族旅行でも行こうかと思っていたのですが、あいにく、この間のボストン近辺は非常に涼しく、そんな気分にもなれませんでした。

この間に1つだけ個人的にGood Newsがありました。私はまだ永住権を持っていないのですが、その最終段階に到達し転職も可能となりました。具体的にはI140というものが承認され、同時に申請していたI485も180日以上経っておりますので、これで晴れて転職可能となったわけです。おりしも面接を進めている過程ですし、なかなかencouragingなことでした。

さて、面接の日取りを決めてからかなり時間が空いてしまいましたので、念のため事前に再確認のメールを送っておきました。アメリカですからね。先方の人事もエンジニアも私の電話面接のことなんて忘れている可能性大です。

電話面接はこれまでの2回と同様、自分の職場で電話を受けることにしました。東部時間で午後6時15分、西海岸では午後3時15分という設定でした。日本では考えられないかと思いますが、午後6時にもなると職場にはほとんど人がいなくなります。その状況で、自分の部屋の鍵を締めて立てこもり、かなり静かな状況を作れます。もし家で受けるとなると、子供達は走り回っていたり、時には泣き叫んでいたりして、なかなか集中できないものです。

今回もほぼ予定通りの時間に電話が鳴りました。受話器を取り自分の名前を告げて緊張の面接がスタートしました。

今回の面接も終わってみれば1時間近く掛かりました。。

面接相手はインド人だと思いますが、かなり流暢なアメリカ的発音でした。もっとベタベタなインド訛り的(?)発音を想定していましたので少し安心しました。ただ、先方はスピーカフォンを使っているようで、プツプツ音声が途切れます。ちょっと聞き取りづらいと文句を言ってみましたが、とりあえず行けるところまでこれで行こうと言われ、そのまま続行。。

今回の面接相手は最初に丁寧に自己紹介をしてくれました。2000年にPhDを取得して、1年半前にGoogleに入社したとのこと。やはりPhDか、学歴資格偏重なんだなぁ、と再認識。大学名やら職歴なども言ってましたが、音声は途切れ途切れだし、適当に聞き流してしまいました。

で、最初の質問は前回と同様まぁ平凡なところからスタートしました。
−今やっている仕事は?
適当に説明すると
−その中で一番Challengingなことは何?
という感じで、まぁ、ここまでは要するに挨拶がわりの会話といった感がします。

多少緊張感がほぐれたところで本当の面接に移りました。まずはアルゴリズム系の質問をすると言われました。前回の面接ではGoogle的なアルゴリズムに関する質問がほとんどありませんでしたので、今回はアルゴリズム中心だろうと勝手に思い込んでいました。なので、予想通りかな?と思われました。

質問内容は、
−整数の配列がある。その重複を除去した配列を再構成するアルゴリズムを説明しろ。

質問自体は至って簡単明瞭ですが、緊張した電話面接では頭も回らなくなるものです。この辺で途切れ途切れの音声が気になったので再び文句を言ったところ、スピーカフォンを止めてくれました。これで音声はクリアになり、仕切り直しです。

最初に思いついたのは、おそらく誰もが思いつくように、予備のvectorを用意して1要素ごとに重複を比較チェックしながら入れ込んで行くものでしたが、私はこれの説明はしませんでした。

私が「vectorを用意して。。」と言い始めると、先方はOKと得意気な口調で言いながら私の説明の続きを促しました。しかし、私は途中で「あ、違う違う」と言って別のアルゴリズムに切替えることにしました。

次に思い付いたのはcounting sortにヒントを得たもので、これを説明しました。私の説明は、
−配列を1回走査してMAXとMINの値を得る。
−(MAX-MIN+1)個の要素を持つカウンタ配列を用意する。
−再度元の配列を走査し、各要素の値に応じたインデックスのカウンタ要素をインクリメントする。
−最後にカウンタ配列を走査し0でない要素のインデックスから値を計算する。

おそらくこんなアルゴリズムは期待していなかったと思うのですが、相手は「その処理時間はどうなるか?」と聞くのでO(N)だと答えると相手も納得。次に、必要なメモリはどれほどか?と聞いてきました。まぁ、予想通りの問答です。私は、「それがこのアルゴリズムの弱点だ」と言って最悪のケースを説明しました。

すると、相手は「メモリ量を減らすにはどうしたら良いか?」と聞きました。私が「トレードオフかな」と言って少し考えると、相手は「トレードオフとはどういう意味か?」と聞いてきました。そこで、「メモリ量を減らして処理時間を増やすアルゴリズムがあるかも知れない。」と答えました。相手は「どんなアルゴリズムになる?」と聞きます。

そこで、私は「方針は2つある。1つは今言ったアルゴリズムを改良する。もう1つは全く別のアルゴリズムに切替える。」と当り前のことを答えました。すると、相手は「別のアルゴリズムを考えてみよう。」と言いました。要するに、彼の欲しいアルゴリズムに到達しないと納得してくれないのでしょう。

私は、「最初に言ったvectorを使うのはO(N^2)の時間が掛かるからダメだから。。」などと相手に聞こえるように独り言を言いながら間をとりました。相手は黙っていました。

少し時間が経った後に「元の配列をソートして。。」と切り出すと、相手はOKと言いながら説明を促しました。説明の続きは「ソートした後、配列の頭から隣の値と比較し、同じ値を排除していく。」というような答えを出しました。すると、やはり処理時間と所要メモリ量について聞かれます。処理時間は長くなりO(NlogN)、メモリ量はクイックソートを使えば、Exchangeに使うテンポラリだけなので最小限で済むと説明。ここで相手はVery Goodと言って、ようやくこの問答は終わりました。

私は最初からソートを使ったアルゴリズムを言えば良かったのかも知れませんが、そう簡単にいくもんでもありません。何となくO(N)のアルゴリズムを説明したかった。。まぁ、単なる自己満足かも知れませんが。。

質問はこの後もまだまだ続きました。続きはまた後日。

0 件のコメント: