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

まず本エントリーですが、Google とのインタビュー記録を見返してみると、non-disclosure agreement に関する記載があったので、質問された問題をここに書くことはできないようです。なので、かわりにインタビュー問題の分野、あるいはその類題を載せたいと思います。

Google とのインタビューということで、できればたくさんのことをお伝えしたかったのですが、力不足から phone インタビュー 2nd ラウンドで撃沈してしまったため、それほどたくさんのことはお伝えできないと思います。他の方のブログなどをあたってみると、より詳細なインタビュー体験記が見つかるかもしれません。good coders code, great reuse というブログのこのエントリーは Google とのインタビューの準備からオンサイトインタビューまで幅広くカバーしているので私のこのエントリーよりずっと参考になると思います 。

いずれにせよ、私自身のインタビューをふりかえってみようと思います。

最初に Google のリクルーターから連絡をいただいたときは、Associate Product Manager (APM) のポジションでインタビューをしないかと言われました。製品の発案や機能設計も非常に面白そうだと思いましたが、開発の方により興味があった私は、リクルーターに Software Engineer のポジションでインタビューができないかどうかたずねました。すんなりOK を出していただき、最初の電話インタビューがその一週間後の11月4日にスケジュールされました。

[1st round interview]
このインタビューでは、履歴書に書いてある私のバッググラウンドの話しを皮切りに、配列から特定の要素を見つけ出す問題、ソーティングアルゴリズムの知識を問う問題、ビット操作に関するコーディングの問題がありました。コーディングは interviewer が送ってきたリンクをたどり Google Doc をシェアし、そのドキュメント上でコーディングを行いました。ビット操作で出された問題は、実際に出された問題とは違いますが、たとえばある正の整数 x が2のべき乗（1, 2, 4, 8, ・・・）であるかどうかを調べるにはどうしますか、というような感じの問題です。いくつもアプローチがあると思いますが、ここでは

if ((x & (x-1)) == 0) {
   System.out.println("power of two!");
}

というようにしてみます。2のべき乗の2進数表記をのぞいてみると、ビットが1になっているポジションはひとつだけで、それ以外のポジションのビットはすべて0になっています。10進数で考えてみても、100や10000といった10のべき乗の数は、全桁のうち1が一か所にしか現れておらず、それ以外のディジットはすべて0ですよね。この if 文はその特性を使っているというわけです。ビット操作は Google のインタビューでわりとよくきかれる問題だと CareerCup （前回の投稿の最後に紹介したサイトです）に書いてあったので、Hacker's Delight などを読みこんでいる方はこの分野に強いのではないでしょうか？携帯電話を肩と耳にはさみつつ、考えていることを声に出しながらのコーディングというのは、非常にやりづらかったですが、最初のインタビューは突破できたようで、次の電話インタビューが翌日にスケジュールされました。

[2nd round interview]
翌日のインタビューは、別のエンジニアとの電話インタビューでした。履歴書の話をすることなく、いきなりテクニカルな質問が飛んできました。スレッドプログラミングの注意すべき点、TCP/IP の基礎知識、そしてまた Google Doc の上でのコーディングでした。コーディングの問題は、集合を取り扱う問題とキューに関する問題でした。集合を取り扱う問題で、私はインデックス i と j を取り違えるミスをしてしまい、それにしばらく気付かずに結構な減点対象になった印象を受けました。そして、キューの問題では、それを解くのに10分近くかかってしまい（電話で考えを口に出しながらだったので、余計考えられませんでした）、もはや interviewer にとってそれだけかかってしまうのは許容限度外のようでした。案の定、3日後に rejection のメールが ;-(

ですが、そのキューの問題というのが非常に面白かったので、ここでは出題された問題に非常によく似た問題を考えます。それは、

スタックをひとつだけ使って、キューに対する操作 enqueue と dequeue をシミュレートしてください。

というものです（実際の問題もスタックひとつという制約つきでした）。以前、スタックを二つ使ってキューをシミュレートというのは解いたことがありました。キューは先入れ先出しのデータ構造、スタックは後入れ先出しのデータ構造です。enqueue は特に問題ないのです。スタックにそのまま要素を突っ込んで、はいこれが enqueue だよ、と言ってやればいいのですから。問題は dequeue の方です。最初に突っ込んだ要素を最初に取り出さなくてはいけません。ですが、スタックが二つ使えれば次のようにして dequeue をシミュレートできます。最初にスタック A に追加した要素 x を最初にとり出すためには、その上に乗っている要素すべてをもうひとつのスタック B にドンドンと積んでいって、最初の要素 x をスタック A から pop できるようにしてあげればいいんですね（積み重なっているお皿の山から一番下にあるお皿をとりたいとき、上に乗ってる他の皿を脇へドンドンと積んでいく感じです）。ところが、この問題ではひとつのスタックしか使えないので、dequeue の際にどうやって底に沈んでる要素を最初にとりだすんだろう、うーんとなってしまうわけです。ふむ、こんな風にしてみてはどうでしょう？

import java.util.Stack;

public class QueueWithStack<E> {
   private Stack<E> stack;
   public QueueWithStack() {
       stack = new Stack<E>();
   }
   public boolean empty() {
       return stack.empty();
   }
   public void enqueue(E item) {
       stack.push(item);
   }
   public E dequeue() {
       if (stack.empty()) return null;
       else return recurse();
   }
   private E recurse() {
       E top = stack.pop();
       if (stack.empty()) return top;
       else {
           E item = recurse();
           stack.push(top);
           return item;
       }
   }
}

21行および24-32行にあるように、再帰を使うと底にあった要素をボンボンと上へ押し上げていけるんですね。 こうすると、先入れ先出しがスタックひとつでも可能になります。実際に出された問題もこれに似たもので再帰が決め手となりましたが、10分は長かったんだなぁ・・・

話は変わりますが、私は再帰関数の定義がかなり苦手です。というのは、関数定義の中で自分を呼び出すというのを頭の中で考えていくと、こうロシアのマトリョーシカ人形のように中へ中へと吸い込まれていってしまって関数の全体像がいつも見えなくなる感じがするからなんです。でも、いつだったかこのサイトの問題を解いてみて再帰が少しだけ怖くなくなった気がします。そのサイトに、再帰に関する私の好きな引用があります。

Trust that the recursive calls return correct output when fed correct input -- make the leap of faith. Look at the partial results that the recursive calls give you, and construct the full result from them. If you try to step into the recursive calls to think how they are working, you'll go crazy.

上記の dequeue もこれにあてはまりますよね。再帰が一番底の要素を返してくれることを信じたうえで自分のすべきことは、底の要素を pop できるように脇によけておいた要素を元に戻し、そしてリレーされてきた一番底の要素を今度は自分が返す、ということになります。

かくして Google とのインタビューは無残に散ったわけですが、新たにコンピュータサイエンス力をつけたり、オープンソースの世界で経験を積んだり、Google Code Jam にチャレンジしたりして、またいつかインタビューにトライしてみたいです。ただしオファー獲得までの道は半端じゃなくきついので、これ以上ないくらいの自信がついてからの話ですが。

CareerCup によれば、Software Engineer のポジションで電話インタビューを受けた candidate のうち onsite に呼ばれるのは約35%で、オファーが与えられるのは、その中の約25%ほどとか。つまりインタビューを受けた人のうち、約9%の人しかオファーをもらえないということになります。APM のポジションで onsite に行ったインド人の友人が一人だけいましたが、やはり reject されてしまいました。APM のインタビュープロセスもどうやら非常に selective で厳しいようです。CareerCup によると、Google の Software Engineer のインタビュープロセスは、interviewer が candidate のパフォーマンスに対し、1.0 から 4.0 のスコアリングをし、それを hiring comittee にコメントを添えて投げるそうです。Hiring comittee も candidate がすべての分野で高得点を取るのは難しいことはわかっているようですが、複数の interviewer が candidate に対して同じ赤旗をあげると（コードが読みづらい、基礎知識がなってないなど）、hiring comittee は直ちに no-hire サインを出すそうです。私もこれにあてはまったのではないでしょうか。あと、突出した能力がある candidate の方が hiring comittee の目を引くとも書いてありました。すなわち、4つのインタビューのスコアが全て3.1という candidate よりもスコアが 3.6, 3.1, 3.1, 2.6 という candidate の方が better ということらしいです。どこまで本当かどうかは分かりませんが、著者は、実際に Google の hiring comittee に属していた経験もあるとのことなので、でたらめな情報ではないと思います。

最近は、こんなニュースもありましたし、本当に Google は超人の集団だなぁと思い知らされます。何度もインタビューをトライしてみたいと思わせてくれる魅力のある企業ですね。