就職活動インタビュー反省記録 with Admob

Admob はモバイル広告の大手の会社で、去年の11月に7億5000万ドルで Google に買収されました。私もちょうど就職活動まっただ中だったので、Admob に履歴書を提出した直後にこのニュースを見て、驚いた記憶があります。MSE の友人から聞いた話では、Google に買収されたあたりから hiring が selective になった可能性があるそうです。もちろん、真偽は定かではありませんが。この5月から Microsoft の Developer になるというインド人の方と話をしたところ、彼の友人のインド人二人が Admob のオンサイトインタビューから自信満々で帰ってきたらしいのですが、結果二人とも reject されてしまったそうです。私の周りでは Admob とインタビューしていた人は一人、オファーを受けた人は一人もいませんでした（インタビューをしていた彼のその後の結果は分かりません）。かくいう私も電話インタビューの 2nd round で reject されてしまいました。

それでは、ここからインタビューの詳細に移ります。

Technical phone interview の一週間前にリクルータの人から電話があり、簡単な会話をしました。専攻は何か、いつ卒業するか、就労ビザは必要か、などなど。会話の最後に、どんなスキルが特に求められるか聞いたところ、「開発言語、ドメインは特にこだわらないから、CS の基礎が備わっていればいいよ」との答えをいただきました。ふむ、Google にも買収されたし、そこと似たような問題が飛んでくるのかなと思い、Google とインタビューをするような気持ちで挑みました。

[1st round interview]
最初のインタビューで出された問題は2つ。私はどちらの問題も CareerCup でおさえていたため、ここは乗り切ることができました。具体的には、

• Singly linked list に cycle があるかどうか、どのように判別しますか。また、cycle があった場合、そのcycle の開始点をどうやって見つけますか
• 100階建てのビルがあります。あなたの手元には同一のたまごが二個あります。たまごは、ある特定の階より上の階から落とすと割れていまいますが、その特定の階およびそれより下の階から落としても割れることはありません。その手元にある二個のたまごを使って、その特定の階を割り出してください。二個とも割れるとゲームオーバーですので、そうなる前に割り出してください。ただし、worst case でたまごを落とす回数が最少になるようなアプローチを考えてください

最初の問題を解くのに、Floyd's Cycle Detection と呼ばれるアルゴリズムがあります。Programming Interviews Exposed の第4章にもありますし、WEB で検索してもすぐに見つかると思います。アイデアとしては、二つのポインタを用意し、list の頭から、ひとつめのポインタを1ノードホップで、もうひとつのポインタを2ノードホップで進めていきます。もしも cycle があれば、それらは cycle のどこかで出会い、cycle がなければ、2ノードホップで進んでいるポインタの方が先に list の末尾に到着するという具合です。cycle の開始点を割り出すには次のようにします。二つのポインタが出会ったら、二つのうちどちらでもいいので、片方のポインタを list の先頭に引き戻してあげます。そうしたら今度は、お互い1ノードホップずつで進めてあげて、次にそれらが出会う地点が cycle の開始点となります。modulo 演算を使うとなぜそうなるのかが分かります。Amazon がこの問題を出したときはその数学的な説明まで聞いていました。

二つ目の問題は正解だけ書きますね。一つ目のたまごを14階、27階、39階、50階、60階・・・と落としていき、それがいずれかの階で割れたら一つ前のステップの階に戻り（50階で割れたら、39階へ戻る）、そこからは一階ずつ増やして二つ目のたまごを落としていきます。これは有名な Brain Teaser の問題ですので、WEB で検索すると「なんでそうなるの？」が見つかると思います（たとえばこちら）。

ちなみに、どちらの問題も Google や Facebook の時のようにオンラインコーディングをすることはなく、すべて口頭で答えを伝えました。数日後に interviewer から "good job!" のお言葉をいただき、2nd round interview に進むことになりました。

[2nd round interview]
このインタビューでは、自分のバックグラウンドを説明するところから始まり、技術的な質問がそれに続きました。

• オブジェクト指向プログラミングの概念を説明してください
• B-Tree のデータ構造について説明してください。要素を検索するときの実行速度はビッグ・オーで何になりますか？
• Model-View-Controller アーキテクチャについて説明してください
• 4GB のメインメモリで 4 byte の整数 1,000,000,000 個をソートしてください

私が時間内に正しい答えを出せなかったのが最後の問題でした。Mergesort の variant を使って部分的にソートしていくというところまで答えたのですが、そのステップを最後まで正確に説明できませんでした。この合計 4TB にもなる 1,000,000,000 個の整数は 4GB のメインメモリに一度に収まりきらないので、分割してソートしていく必要があります。これには External Sorting というソーティングを使いますが、申し訳ないことに具体的な数値に関しては今計算しているところです（メインメモリに用意する入力バッファ、出力バッファの適切なサイズ、K way merge をする際の multiple pass の数など）。 Database Management Systems の第13章と以下のビデオで勉強中です。



あと、MVC アーキテクチャでひとつ腑に落ちないことがあるのですが、Model と View と Controller の円があってそれらが線で結ばれている典型的な MVC アーキテクチャの図、あの図の view type は何でしょうか。コード依存などを表した static view なのでしょうか、それともシステムの実行時の振る舞いを表した runtime view なのでしょうか？MSE の Architecture のクラスでアーキテクチャの文書化について習ったまず最初のことは、view type をはっきりさせなさい、ということでした。コード依存を表した static view なのか、実行時の振る舞いを示した runtime view なのか、物理的なデバイスの割り当てを示した allocation view なのか？これらをごちゃごちゃにして、アーキテクチャの図を描くと、ソフトウェアシステムの特性の分析が非常に難しくなります。たとえば、変更容易性はコードの変更に関わるということから、static view で議論されるべき特性で、runtime view で議論できる特性ではないと思うのです。逆にパフォーマンスは、runtime view で議論されるべき特性で、モジュールの依存を示した static view で議論されるべき特性ではないと思います。典型的な MVC の図は、データの受け渡しをしているように描かれているため、一見 runtime view なのかなと思いますが、一方で Model, View, Controller の開発、保守を独立に行えるという記述も添えていることがあるため、static view のことを言っているようにも聞こえます。どうでもよいことかもしれませんが、view type をはっきりさせることは、Architecture のクラスで学んだ重要なことのひとつだったもので。"A picture is worth a thousand words" と言われるように図は重要で、一度に多くの情報を与えることができますが、逆に100人のエンジニアがそのアーキテクチャの図を、自分の "a thousand words" で解釈してしまい、その解釈が一致しない恐れもあるわけです。100人のエンジニア全員が同じ解釈をできるよう、アーキテクチャの図を描く際は、箱や線には必ず凡例をつけるなどして、図が示す意味の曖昧さを取り除く努力をしなければいけません。出された問題とは直接関係ないことなのですが、電話インタビューの後にふと思ったことだったのでここに書いてみました。

結果、Admob からは 2nd round の電話インタビューで reject されてしまいました。iPhone 上の開発が活発に行われているとも聞きましたし、Admob とインタビューしていたその友人が興奮気味に語っていましたが今や Google の傘下ですし、もしもインタビューをパスできれば、きっと面白い仕事が待っていることと思います。

他にもインタビューをした会社がありましたが、これにて就職活動インタビュー反省記録を終わらせたいと思います。今後は、Natick や Boston のこと、空き時間に趣味でやっている勉強のこと、その他日々のことなどを書いていきたいと思います。これからもよろしくお願いいたします。