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)のアルゴリズムを説明したかった。。まぁ、単なる自己満足かも知れませんが。。

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

Googleの面接 2回目の結果

時間切れで後味の悪い形で終わった2回目のPhone Interview(電話面接)でしたが、4日後にGoogleの別の担当者からメールが来ました。週末を挟んでましたので、実質2 business days後にメールが来たわけです。さっさと処理してくれたもんです。

題名は"Availability for ..."で始まり、内容は大体想像できましたが、SPAMかもしれませんので、中身を確認してみると、Congratulations on passing ...となっており、とりあえず次のInterviewに進めることが分かりました。最初の面接で言われた通り、もう1回Phone Interviewを受けることになるようです。

今後3週間で都合の良い日時を複数教えろとありました。私の方は急ぐ理由は全然ありませんし、バケーションシーズンですし少しゆっくりしたかったので、2週間以上先の8月の終わり頃の日をいくつか挙げておきました。こういう場合には早い日時を答えた方が良いのでしょうかね？ちょっと失礼だったかな？ま、Googleはそんな下らない理由で合否を決めたりしないでしょう。

メールの中では、他の会社と面接を進めているか？とか他からOfferは受けているか？もしそうだったらExpediteできるよ、などと書いてありました。そんなの最初の面接の時に回答したんだけどと思いつつ、ま、アメリカだし担当者が変わったらよくあること、仕方ないか、と思い直し、転職活動はしていない由返答しておきました。

そして、その次の日の遅くになって、Please Confirm Phone Screenなるメールが再び2人目の担当者から来ました。内容は面接の日時と面接相手の名前が変わっただけで前回とほとんど同じでした。それにしても連絡してくる人がなぜこんなコロコロ変わるんでしょうね。しかし、"Screen"とは、少し言葉遣いに気を付けて欲しいな。西海岸の人はあまり気にしないのかな。。

私が回答した日の中で一番早い日が指定されていました。私から応募したわけでもないのに、なんだか急がされてるような気分です。。今度の面接相手は名前からしてインド人のようです。この業界にいるとインド人が多いことを痛感します。ちなみにカリフォルニアにいる私のマネージャも、辞めてしまった何人かの同僚もインド人なので、どちらかというと付き合いやすい印象があります。

ま、ともあれ、とりあえずGoogleの面接はまだ進んでいるわけで、もう少し良い夢を見ていられるようです。ただ、とにかく人気の高いGoogleですから、ほんの一握りの優秀な人しか入れないはずで、あまり気分良く夢見心地になってもいけないでしょう。。。まだ2回電話面接に通っただけですからね。今後、現実に突き落とされた際のことも考えておかないと。。。妻なんか「あまり急いで引越しになっても困る」などと、余計な心配までしてます。夢が夢のまま終わった時のことを考えると、あまり浮かれてもいられないと思います。。

何とかあと1回通ってMountain Viewでの面接に招かれてみたいものです。。

Google Interview (電話面接その2)

最初の電話面接からちょうど1週間後にGoogleの別の担当者から"Please Confirm Phone Screen"と題するメールが来て2回目の電話面接の日取りが決められました。最初の面接の時に伝えておいた希望日時通りになりました。それにしてもInterviewを受ける相手に対して"Screen"とは失礼な！！(ま、きっと何も考えてないんでしょう)

2回目の面接はもっと難しい質問になるということでしたので、色々調べたり勉強したりしました。アルゴリズムの本なども買って今さらながら読み直してみました。コンピュータ関連の用語は普段使いますので問題ないですが、大昔に日本で勉強した数学用語なんかも英語で言えないと困りますから、とりあえずアルゴリズム関係で使いそうな用語はざっと見ておきました。今さらですが、階乗はFactorial、多項式はPolynomial、帰納法はInductionというんですね。。

2回目の面接はネットワークとUNIX関連がほとんどでした。最初は30分と言ってましたが、結局50分くらい掛かりましたね。なかなか疲れます。今回はTechnical Interviewということで、技術そのものが問われますからかなり緊張しました。

その質問内容ですが、こんなのからスタートしました。
−今までで一番難しかった仕事は？
ま、よくありそうな質問ですね。が、私は逆に焦りました。こんな平凡な質問でなく、もっとGoogleらしい質問を想定していたからです。もう随分昔にやったプロジェクトの説明を適当にしましたが、先方は理解してるのかしてないのか特に反応もなく、次の質問に進みました。

ま、ここからが本番ということでしょう。まずは、
− ◯◯◯(ネットワークプロトコルの名前)とは何？
うーん、バカにしとるのか、というような質問でしたが、これもどの程度まで深く答えられるかが鍵なんでしょうかね。私は昔プロトコルの設計をしたことがあるので、そんな話を交えながら説明しました。この後の質問として覚えているところとしては、、
−どのようにコネクションを張るか？
−◯◯◯番号とは何？
というところでした。その後はネットワーク機器の質問がいくつか
−◯◯と◯◯の違いは何？
−◯◯ではどうやって宛先を見極めるの？
といったようなとこでした。

次にUNIX系の質問に移りました。
−◯◯はどうやって消去する？
うーん、やはり最初はバカにしたような質問になるようです。次の質問は
−"◯◯"という名前の◯◯はどうやって消去するか？
いきなり引っかけ問題でした。
次の質問
−◯◯コマンドとは何をするもの？
これは英語圏の人はコマンド名に釣られて安易に答えてしまうのでしょうか。私は日本人なんで引っかからずに済んだと言えるかも知れません。次はこれに関連して、
−◯◯◯◯を受け取るとどんな動作をするか？
といった質問が来ました。これも適当に答えると、
−◯◯レベルに渡らない◯◯◯◯は何？
といった質問をされました。質問の連鎖はよく練られているようです。UNIX関連の最後は、
−◯◯◯◯プロセスとは何？
という質問でした。

ここまでの質問は答えるのにそんなに苦労しませんでした。要は知識があるかどうかの問題で、知っていれば簡単に答えられますし、知らなくてもそれっぽいことを言うしかありません。先方は私の解答に対しては"OK"としか応答せず、それが当たっているのか外れているのかさっぱり手応えがありませんでした。そして、その後が大変でした。

紙とペンを用意しろというので覚悟はしましたが、ま、彼らの検索エンジンの一部の設計をしろというような内容でした：
−◯◯台のマシンがあり、ファイル中に膨大なQueryが格納されている。Queryのランキングを取り出すソフトウェアを設計しろ。

細かい数字はあえて臥せておきますが、私には電話面接にふさわしい質問とは思えませんでした。僅か5分か10分でできるようなものとも到底思えませんでした。私は、こんな短時間でやるのは難しいよ、とか、ここはRadix系のサーチが良いかな、などとブツクサ文句言いながら説明を試みました。結局、途中で時間切れになってしまったので、自分としては不満の残る後味の悪い結果となってしまいました。。

この時間切れの後に、私の方から質問があるか？と聞かれました。もうかなり頭の中が真っ白だったので、もうどうでもいいよ、と思いましたが、とりあえず、Google内のプロジェクトは何人くらいの単位でやってるの？とかデッドラインなどはどうやって決めてるか？など当たり障りのない質問をして、最後に礼を言って切りました。

後味の悪い最後でしたので、この週末は電話で質問されたことばかり考えていました。あの時、もう少し頭が回っていれば、こういう風にも答えられたなどと考えたり、あるいは、私のたどたどしい英語のせいで落とされたりしないだろうか？などと考えたり。まぁ、考えても仕方ないのですが。。これで終わりかもなぁ、などと思いながらも、妻には「もう1回くらいあるといいなぁ。」などと言いながら少し引きつった笑顔を見せるのが精一杯でした。

果して1週間後にどのような回答があるでしょうか。。