2007/09/04

Google Interview (電話面接その3続き)

3回目の電話面接から1週間が経ちましたが、その後、Googleからは音沙汰がありませんでした。1週間も連絡がないということは不合格だったということでしょう。もし私が先方にとって欲しい人材なのであれば数日で連絡が来てさっさと処理を先に進める筈です。残念でした。

不合格だったとはいえ、その理由などを自分なりに分析する意味で、今回の投稿を書いてみたいと思います。読者の方々の今後の御参考になれば幸いです。それでは、前回の投稿の続きから。。

アルゴリズムの質問が1つ終わったところで、今度はUnix/Linux/Internalの質問をすると言われました。今回の面接はアルゴリズム中心になると勝手に思っていたので、思惑が外れた感じがしました。

まずは、
−ソフトリンクとハードリンクの違いは?
というところからスタートしました。とりあえずは、ほっとするような質問から始まるものですが、この質問は、ここから始まる連鎖的な質問の入口に過ぎないわけです。
−なぜハードリンクはFS内に限定される?
−ハードリンクの片方を消去するとどうなる?
特段難しい質問ではありませんが、こういった質問に答えていくと、次第に深い質問につながっていくわけです。
−ハードリンクでは複数のファイルで1つのinodeを共有すると言ったが、inodeにはファイル名が記録されているのか?
これにはNOと答えると、
−それでは1つのinodeと複数のファイルを関連づける仕組は何?
と聞かれました。ここまで来ると私は、ディレクトリだったかな?と思いつつも、「うーん、忘れたなぁ。」と言って少し間を取りました。

すると、先方はすかさず
−それでは、inodeにはどんな情報が入っている?
と聞きました。こんなのは随分昔に勉強したことなので記憶も曖昧でしたが、先ほどファイル名は入っていないと答えましたので、それ以外の適当なものを答えました。
「ファイルサイズとかファイルのパーミッションとかリンク数とか、あとデータブロックの番号・・」などと列挙していきました。

そして、私が「indirect block...」と言って説明を続けると、先方は「それは古いね」などと言ってきました。「古くて悪かったな!」とは言い返しませんでしたが、とりあえず笑って誤魔化して、SVR4の時代にやった仕事について少し触れました。

先方は私の知識が古いという印象を持ったのかも知れませんね。。

そして、再び
−それでは1つのinodeと複数のファイルを関連づける仕組は何?
に戻りました。とりあえず「inodeと名前を関連づける名前解決の仕組が、inodeの外にある筈で・・」と言うと、先方はOKなどと言い、私が「うーん、何だったかな?思いだそうとしているんだけど・・」と言い、「ディレクトリだったかな。」とつぶやいたところで、先方はGoodと言い、この一連の質問は終わりました。

次にネットワーク一般の質問をすると言われました。アルゴリズムの質問ばかり想定していたので、またアテが外れた感じがしました。
−ネットワーク上でホスト名からターゲットにたどり着く仕組を説明しろ。
例えば、ブラウザにサイト名が入力されたらどういう処理を経てターゲットシステムに要求を投げるのか?という、ま、要するに名前解決の基本を聞かれているわけです。この職はUnix/Linux系らしいで、とりあえず、nsswitch.confから始まってDNSあるいはhostsファイルに至る処理を説明しました。途中で、
−resolv.confには何が入ってる?
といった質問もありました。次に、
−DNSサーバはどういう処理をする?
という質問でした。これは私の知識がちょっと曖昧でした。とりあえず、「IPアドレスとホスト名の関連付けを行うキャッシュを持っている筈で・・」と答えると、当然のように
−キャッシュに情報がなかったら?
と追い撃ちを掛けられるわけで、「外部のFirst level serversに問い合わせにいく。」などと適当に答えました。すると、
−どのFirst level serversに問い合わせる?
−全てのFirst level serversが同じ情報を持っているのか?
などと聞いてきます。私は「Good question」などと言って考える間を取ろうとしました。すると、先方は、
−もし分からなかったらDNSサーバを設計してみろ
などと言ってきました。こんな基本的なこと、もう少しおさらいしておけば良かったなぁ、と後悔しましたが、とりあえず、頭に浮かぶ限り「各ドメインに相当するサーバがあって・・・例えば.comとか.eduとかに応じて問い合わせるべきfirst level serverのマップを管理して・・」と答えていきました。先方はOK..などと言って説明を聞いていましたが、最後にGoodと言って、ここで一連の質問が終わりました。

面接後に振り返ると、最初にrootサーバに問い合わせに行くという点や、連鎖的に問い合わせにいくという点の説明が抜けていました。この点は減点対象だったと思います。

事前にちょっと知識を整理しておけば・・と後悔しても始まりませんが。。

次に、先方は、「これは最初の面接か?」などと聞いてきました。「3週間位前にも電話面接を受けた」と答えると、「いや、この前の面接で何を聞いたのかといった情報がなくてね。。」などと本音を漏らし、「それじゃ、1 billion queriesの問題は聞かれた?」などと言ってきました。

前回の電話面接の最後に聞かれた忘れもしない質問です。私はすかさずYesと答え「あれは大変な質問だよね」などというと、相手も"Yeah, that's tricky one"などと同意してくれました。

このあたりでもう40分以上経過していて、もうこれくらいでいいんじゃないの?と思いましたが、相手はしばらく考えた末、もう1問アルゴリズムの質問をすると言ってきました。これが最後の質問でした。
−整数の配列がある。正の数を前半に負の数を後半に持ってくるアルゴリズムは?

全く簡単明瞭な質問でしたが、あまりにもシンプルな質問だったので、裏があるのではないかと思い、私は2回くらい聞き返してしまいました。「これは最初の質問の続き?」とか「ソートする必要はあるの?」とかとりあえず周辺に裏がないことを確認するのに一生懸命になってしまい、相手は「クドイ」と思ったかも知れません。。

私は、まずは最もnaiveなところから始めることにしました。
「これが最終回答じゃないよ。」と釘を差しながらも、最初のはちょっとnaive過ぎたかも知れません。
「2つの配列を用意して片方に正の数を片方に負の数を入れていき、最後に合わせる。」
バカみたいな回答です。。

相手は
−配列を1つにできない?
と聞くので、できると言って
「2つのインデックスポインタを用意して、片方は配列の先頭に、片方は最後尾を指しておく。正の数を前者のポインタの位置に、負の数を後者のポインタの位置に入れ込んでいく。」
と説明。

相手はGoodと言い、
−それじゃExtraの配列をなくすことは可能?
と聞いてきました。私は余計な時間を掛けずに一気にここに来るべきだったのかも知れません。もちろん、できるはずで、私が
「exchangeを駆使した方法があって、例えば、配列を走査して負の数を見付け、見付かったら隣の値を見て正だったらexchangeして、バブル的に繰り返す。。」
などと説明していたら、途中で、相手は「あ、こんな時間だ。そろそろ終わりにしよう。そちらから質問ある?」などと言いました。

え、続きがあるのに・・と思いましたが、質問が終わった解放感から、私はOKと言い、相手のグループについて当たり障りのないことを質問して終わりにしました。

「この職はLinuxのSystem Adminとソフトウェア技術者の中間的なものだ。」と言うので、
「私はFlexibleでどちらにも対応できるよ。」と返しました。
「え、System Adminやったことあるの?レジメには見当たらないけど。」などと突っ込まれましたが、適当に過去の仕事を説明しました。

どうも相手は急いでいる感じがしましたので、あまり突っ込まずに、最後に礼を言って電話を切りました。。

しかし、電話を切ってから1分もしない内に、最後の質問でもっと良いアルゴリズムが頭に浮かんで来ました。クイックソートで使うパーティションを利用するだけでOKじゃないか・・

どっと疲れが襲ってきました。。

それでも、電話を切ってからの感触としては、今回の方が落ち着いて話ができたため、自分としては前回よりも良いと思えました。前回の電話面接では、最後のヒドイ質問では散々でしたが、それ以外の質問でも2点ほど曖昧な点や誤回答があり、なによりも非常に緊張していたため、不安だったものです。

前回の面接相手はこちらが何を言ってもOKとしか返さなかったのに対し、今回の面接相手は最後にはGoodと言って区切りましたので、こちらも良い気分になっていただけかも知れ
ません。別に私の回答が良くてGoodと言ってたわけじゃないのでしょう。。

結果は、今回は不合格だったわけで、自分の感触と相手の持った印象とは違うものです。よくよく分析すると、今回は
− DNSサーバの動きについて説明が曖昧
− ベストな回答に到達するまで回りくどい
− 英語に問題あり
− 知識が古い
− クドイ
などなどが減点対象となるでしょうか。。
(前回の方が酷かったような気がするのですが。。)

さて、
終わってみれば、ま、最初から予想されたことではありますが、残念な結果でした。
私もまだまだ勉強が必要です。でも、非常に良い経験になったと思います。

このプロセスの間はトーナメント形式の試合みたいなものでした。
1回、2回と進んだ直後だけ嬉しくて、でも、すぐに次のために準備する必要がありました。結局、最後まで勝ち進まない限り、それの繰り返しです。大昔に何かスポーツのトーナメント試合に参加した頃の心境を思いだしました。日本では夏の高校野球のシーズンでしたが、球児たちも同じような心境だったのでしょうかね。

最初の連絡をもらってから2ヶ月近く。Googleに入れたら・・などと、ほんの少しの間だけでも良い夢を見られただけで、思い出に残る夏になった気がします。

0 件のコメント: