Life is beautiful

　マイクロソフトの採用面接がユニークであることは、「ビル・ゲイツの面接試験－富士山をどう動かしますか」という本で一時話題になった。もちろん、私自身もマイクロソフト本社で面接官として数え切れないほどのエンジニアの面接を担当し、自分なりに工夫して作り出した試験問題を幾つも用意していた。今日は、その一つを披露して、得意のうんちくを展開しよう。

［問題］
二次元座標上に、それぞれの辺がX軸・Y軸と平行に置かれた長方形Aと長方形Bがあるとする。その時、長方形Aと長方形Bが一部でも重なるかどうかを判断する条件式を書け。フォーマットは、CやJavaなどのコンピューター言語でも良し、単なる数式でも良い。制限時間は３０分。ただし、考えていることを声に出し、ホワイト・ボードを使って自分の考えのプロセスを説明しながら解くこと。

　もし、これからプロのソフトウェア・エンジニアを目指そうという理科系の学生がこのブログを読んだのであれば、いったんここでストップし、まずは自分自身でこの問題にぜひチャレンジして欲しい。とても良い頭の体操になるはずだ。

　マイクロソフトにおける採用面接、特に大学を卒業したての新人の採用面接で一番重視しているのは、「raw intelligence」である。直訳すれば、「生（なま）の知性」である。そこには、「知識は必要に応じて付ければ良い。一番大切なのは、新しい知識をすばやく見に付け、それを応用して難しい問題を解決する知性だ」という会社としての確固たる信念がある。

　その方針に従って学生を面接するには、単に「今まで学校でどんなプロジェクトをしてきたの？」とか、「どんな言語でプログラムが書けますか？」などという悠長な面接をしていてもほとんど役に立たない（そもそも、その手の情報は既に提出された履歴書に書いてある）。自分の受け持ちの３０分から１時間の間に、どれだけその人の「raw intelligence」にチャレンジするディスカッションができるかが勝負となるのだ。面接官によっては、先の本のタイトルにもあるように、「あなたなら富士山をどう動かしますか」などと、あえて簡単な解答が無い問題を出すことにより、脳みその柔軟さを測る作戦に出たりするのである。

　私の場合は、上の問題のように一見シンプルだが複数の解き方のある問題を出すことにより、（１）問題を解きながら、どうやったらより簡単に答えにたどり着けるかを探る習慣があるか、（２）複雑な問題をより単純な複数の問題に分割して考えるというトレーニングを受けているか、（３）解答のエレガントさ・シンプルさにこだわるタイプか、を測る作戦を採用していた。

　この問題を初めて見た場合、ほとんどの学生は、まずは２つの長方形のさまざまな交わり方をホワイト・ボードに書き始める（学生が既にこの問題を解いたことがあるどうかは、この段階で見極めなければならない。そうであると判断すれば、別の問題に切り替える）。そこで多くの学生が、この問題が意外に複雑であることに気が付く。長方形の交わり方には上下左右の関係を別々に考えれば、１６通りもの交わり方があるのだ。ここで、その１６通りの交わり方をそれぞれを式にして、ホワイト・ボードを埋め尽くし始める学生がいるのだが、そのアプローチを取ると、ほとんどの場合規定の時間内に答えを書き終えることが出来ないし、作業の煩雑さゆえにどこかで必ずケアレス・ミスをする。こっちは、そんな煩雑な作業に取り掛かる前に、「こんなに手間だけがかかる問題をこの面接官が出すはずがない。もっと簡単な方法があるはずだ。」と気が付くような学生を求めているのである。

　そこで、賢い学生は、ここで一旦手を止めて考え始めるのである。「もっと簡単に解く方法があるはずだ。なんとか、この問題を、より単純な複数の問題に分割できないだろうか？」。ここまで来れば、次のステップにたどり付くのは時間の問題である。そして、「ひょっとしたら、X座標とY座標を別々に考えても良いのではないだろうか？」と気づくのである。先ほどの図を見ながらこれを検証するにはそれほど時間がかからない。

　X座標だけに着目して考えれば、交わり方は４通りだ（AがBを含む場合、BがAを含む場合、AがBの左端と重なっている場合、AがBの右端と重なっている場合）。そしてそれぞれの交わり方の検証には、2回もしくは３回の比較演算が必要である。これならホワイト・ボードを埋め尽くせずに式が書ける。多くの学生は、このアプローチが正解にたどり着く道と信じて、式を丁寧に書き始める。

　この問題のすばらしい所は、これでもまだ「最もエレガントな」解答では無いことだ。多くの学生はこの時点で満足してしまうので、「良く出来たね。でも、もっとエレガントな方法があるんだけど気が付かない？」と催促してあげる必要がある。ここで、相手の目がチャレンジ精神に燃えてキラキラ輝き始めたらとても良いサインだ。

　この次のハードルは、就職がかかった面接というプレッシャーのかかった場で越すのは学生には少し難しいので、「確かに交わり方は４通りだけど、もう少し簡単に交わっているかどうかをテストする方法があるんだよ」などのヒントを出してあげる必要がある。この段階で「交わらない場合は（AがBより右にある、AがBより左にある、の）２通りしかない」ことに気が付けば、もう正解は目の前である。後は自動的に、交わらないことの検証には比較演算が１回づつしか必要ないことに気が付き、結果として、トータルで４回の比較演算とわずかな論理演算だけ（プログラムにすればわずか2行で）でこの問題が解けてしまうことに気づくという仕掛けである。一部の学生は、この段階で、最初から交わらない場合を考えていれば、XY座標を分割して考える必要が無かったことに気がつくのだが、そこまで３０分でたどり着けるのはごく一部の学生だけだ。

　ちなみに、この手の問題を使って面接する場合には、学生を適当に励ましながら、正しい方向に導いてあげることが必要だ。そのプロセスの中で、こちらのガイドラインやヒントにどのくらい敏感に反応してくるか、エレガントな解答にどのくらいこだわっているか、などかが分かってくるのだ。

　もし、理科系の学生でこの問題が解けなかった人がいたとしても、ショックを受ける必要はない。大切なことは、上で述べたような、よりシンプルでエレガントな解決法を常に探す気持ちを大切にして、自分自身を鍛えて行くことだ。一つの答えが出たところで満足せずに、「もっとエレガントな手法はないか、もっとシンプルな答えはないか」と考える姿勢を養うことが大切だ。学校の試験であれば、答えを提出してしまえば終わりだが、仕事でろくでもないプログラムを書いてしまうと、後々までタタられるのだから。

［追記］好評に付き、「ビル・ゲイツの面接試験－クイズ編」というのも書きました。面接官としてのうんちくは抜きにして、単に問題だけを書いたので、頭の体操だと思ってチャレンジしてみてください。