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週間後にどのような回答があるでしょうか。。

"Greetings from Google" (Googleの面接)

7月の初旬にこんな題名のメールがGoogleの人事から送られてきました。
Linux系のSoftware EngineerのJob opportunityがあるから興味ないか？
といった内容でした。要するに求人案内です。
寝耳に水といった感じです。

今やMicrosoftも脅かす程の存在になってしまったGoogleですから
転職先としての人気は非常に高く、1ヶ月に10万件もの応募があるとも聞きます。
そんな人気企業に入れるような人は非常に優秀なごく僅かな人達で、
非常に狭き門であるには違いないのですが、
折角お声を掛けてくれたのだから応募だけでもしようと決めました。

ちょうどサンフランシスコに出張中でバタバタとしていたため
返事は2日後になりました。
返事をすると、向こうからすぐに返事が返ってきました。
少し詳しいJob Descriptionが書かれており、
勤務地はMountain View, Santa Monica, New York, Seattleの他
アイルランド、オーストラリアの都市など7箇所で募集しているとのことでした。
私の住んでいるボストン周辺はありませんでしたが、
とりあえず最初のPhone Interview(電話面接)のアポを取りました。

ま、最初のPhone Interviewですので、人事的な内容だろうと思い、
特に準備もしないで臨みました。内容は、職の説明から始まり、
私が現在転職活動をしているか？どの勤務地に興味があるか？
など聞かれました。
その後、自分のスキルについて自己採点しろということで、
C, C++, Java, SQLなど全部で10項目くらいを0〜10の
どのレベルかを問われました。
Googleで働いている技術者のレベルは大体4〜7のレベルだと言うので、
ま、コメントを加えながら適当に答えました。

その後、技術的な質問をしたいから、以下の3つのどれが自分に
ふさわしいものか選べといわれます。
−ソフトウェア技術
−システム管理
−データベース技術(だったかな？忘れた)
私はソフトウェア技術と答えました。
すると、ソフトウェア技術関連の質問を3つすると言われました。

最初の質問は、◯◯◯ソートとはどういうもので、
どれくらいの時間が掛かるものか？というものでした。
学生の頃習ったのは思い出せますがアルゴリズムは忘れました。
大体、ソートにも色々なアルゴリズムがあります。
大学を卒業したばかりの人の方なら答えられるでしょうか。
これは困りました。のっけからつまずくのも嫌なので、
とにかく頭に浮かぶ限りそれっぽいのを説明しました。

どれくらい時間が掛かるか？についてもLog Nのオーダと答えるのが
やっとでした。しかし、正解は違いますね。。
更に追い撃ちを掛けるように、What about the worst case?
と聞かれ、これもしどろもどろ答えましたが、違いました。
いきなり出足からつまずいてしまったようでした。

次の質問は「2の◯◯乗は何か？」というもので、いきなり簡単になりました。

3つ目の質問は次の4つを速い順に並べろというものでした。
−◯◯◯◯アクセス
−◯◯◯◯スイッチ
−◯◯◯◯シーク
−◯◯◯◯リード

とりあえず、ここまで答えると、Greatと言われ、
Now you have another bonus question.
などと1問追加してきました。3問て言ってたのに。。
電話の向こうで何やら紙をめくっている音が聞こえてきます。

最後の質問は、巨大な配列があり、
それらのどのビットが立っているかを調べる最速の
アルゴリズムを説明しろ、というものでした。

これも適当に答えると、相手はそれが最速か？などと不満そうで、
考え直して、別の解答をしましたが、それもダメでした。。

終わってみれば50分ほどになってしまいなかなか疲れました。
こちらとしても、満足な解答ができた気がしませんでしたので、
少々不安でしたが、直後にメールが来て、今後の日程やら
次のPhone Interviewの準備の仕方など詳しい内容が送られてきました。

Phone Interviewは更に2回くらいあり、それらを通るとOn-siteでの
Interviewがあるとのことで、全体で2ヶ月から2ヶ月半掛かる
ということでした。なかなか気の長い話です。
ま、そこまで行ける人もごく僅かなので、
私が心配することでもないかも知れませんが。

技術的には次のInterviewで聞かれそうな項目が列挙してあり、
準備しとけということで、なかなか親切な内容でした。
今までの転職活動で、先方の会社の人事の人から
事前に準備しておく内容までアドバイスを
受けたことなどありませんでしたから、何とも奇妙な気がします。

1週間以内に別の担当者から連絡が行くとのことでしたが、
ちょうど1週間後に2回目のPhone Interviewのスケジュールが
言い渡されました。
次は8月の初旬。
この調子で続けば確かに2ヶ月とか掛かるのでしょう。。
とりあえずもう1回くらいは通りたいものです。。

初投稿

世の中がブログで埋めつくされるようになった今さらですが、
遅ればせながら初投稿です。

まずは、自己紹介的なところから。。

渡米したのは2000年春。
最初はニュージャージ州に1、2年程度の予定で赴任しました。
しかし、1年もいると、もっと長くいたくなり、帰任命令に従わず転職。
その後は色々とありました。

現在はボストンの郊外にて家族４人で生活してます。
「ボストン？どこそれ？」
と思うかも知れませんが、
最近、松坂が入団したレッドソックスのある地です。
アメリカの北東部の端にあります。
冬はむちゃむちゃさむいです。

４月になってもこんな日が→
ここにはかれこれ5年住んでいます。

職業はソフトウェア技術者。
日々、プログラムと格闘しております。

これから時々書きたいと思いますので、
よろしくお願いいたします。