Aggressive Style 5

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

googleのカンファレンスと、日本の就職事情に関する批判など

前編:Google Developer Dayのクイズ問題について

本家ブログより引用すると、このイベントは、

Google Developer Day を今年も 9 月 28 日(火)、東京国際フォーラム(サテライト会場を京都で予定)にて開催することが決定しました。Google Developer DayGoogle が毎年世界各地で開催している開発者向けイベントで、日本では毎年開かれており、今年で 4 回目になります。

先月、サンフランシスコで開催された Google I/O では数多くの新技術や新プロダクトが発表されました。その流れを受けて、今回の Google Developer Day では HTML5ChromeAndroidGoogle App EngineOpenSocialGoogle Maps APIGoogle Wave、Go、Google Buzz などの Google が提供する API や技術、Google が協力するオープンテクノロジーをテーマに、昨年以上のセッションを開催します。Google のソフトウェアエンジニアや Googleのテクノロジーに精通したパートナー、コミュニティの方々が一同に会する場となることでしょう。

と、言うわけで前半は問題。後半はちょっとした愚痴でお送りしたい。

「経路最適化」の問題を無断公開

Google Developer Dayに参加する為には、googleが出すクイズの問題に正解しなければならない。今日はその内の問題の一つを無断公開したい。入力のリンク先は残念ながら保存してないので公開できないが、問題の内容だけでも見てみると良い。



巡回セールスマン問題

この問題はグラフ理論と言う数学の問題の一つである、巡回セールスマン問題であると考えた。問題のアルゴリズムソースコードを作ってないので、巡回セールスマン問題の説明をするのに留める。

グラフ理論

まずグラフ理論についてwikipediaから引用すると、「点と点同士を結ぶ線に注目した学問がグラフ理論であることが分かる。

例えば電車の乗換案内図を考える際には、駅(ノード)がどのように路線(エッジ)で結ばれているかが問題であって、線路が具体的にどのような曲線を描いているかは本質的な問題でないことが多い。たとえば、乗換案内図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。(実際には凹になっている箇所のある山手線が楕円を描いているなど)電車で移動する人を対象とした乗換案内においては、駅と駅の「つながり方」が主に重要なのである。

このように、「つながり方」に着目して抽象化された「点とそれをむすぶ線」の概念がグラフであり、グラフが持つ様々な性質を探求するのがグラフ理論である。つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフという。矢印のないグラフは、無向グラフという。

重み付きグラフ




上のような図における数字は各地点を移動するのにかかる時間(分)である。このように線に時間などの重みを持ったグラフの事を重み付きグラフと言う。

A地点→C地点に速く着くには?

ではここでA地点からC地点に速く着く時間を考えてみる。今回の場合、4通り行き方があるのでその全てを列挙してみる。

  1. A(上)→Cまでかかる時間:17分
  2. A(下)→Cまでかかる時間:19分
  3. A(左)→B→Cまでかかる時間:5分+11分=16分
  4. A(右)→B→Cまでかかる時間:7分+11分=18分

最短経路問題

と3の行き方で行くのが一番速いことが分かる。道が複数本ある場合でもこのように総当たりで時間を計算すれば最短ルートを見つける事ができる。このように重み付きグラフにおける2つの点を結ぶ経路の中で、その重が最小になるような経路を選ぶ問題の事を最短経路問題*1と言う。
が、実際電車などでもA駅からB駅まで行く方法って複数通りある場合が少なくない。そこでダイクストラ法などの方法が考案されている。

巡回セールスマン問題(wikipedia)

ここで巡回セールスマン問題とは全ての地点を一週してその重みの合計が最小となるような経路を発見する問題である。これは今回のgoogleの問題の内容と一致する。ここで今回のgoogleの問題では「2つの地点は幾つかの直線の道で結ばれている。又初期値として与えられた点の個数に依らず、1周するのにかかる時間が最短となる物を探せるアルゴリズムを」と言うことだと思った。

又巡回セールス問題を解決する為のアルゴリズムが、複数あるので問題に合わせ的確なものを選択するのが難しいと思った。「△△は使うな」とあるが、その△△が最短時間を求めるものではない可能性も高いと見た。と、自分が考えたのは大体ここまで。実際にソースは書いていないけれども人に「何故このアルゴリズムを?」と聞かれて答えられるようにしておくのが望ましい気もする。

後半:日本もこういう面接をしてくれればいいんだけどなあ

今回Google Developers Dayの問題を載せた理由について、google具体的な問題などからその人がどのようなアプローチで解決したか?どのような技術力があるかを見る問題を出題するのが上手いと言う点を言いたかった。又多くの日本の大卒の就職事情を語ったブログでは、飽くまで日本の事しか述べてないので他国の企業と比較してみたいと思ったからだ。

Googleが素晴らしい製品を作っている一因は、面接にあると思う。さてGoogleの面接試験、一体どのような質問をされるのか?/GIGAZINEなどを見ていても、数学や心理学のバックグラウンドを活かし、解決策を筋道建てて説明させるような内容が多い。要は勉強したことを直接活かしやすい問題である。ただただ知識を詰め込むだけでなく、きちんと運用できなければダメだけど。もちろん日本の場合の技術面接などでも同様ではある。

日本の場合メーカーを除き面接で学生時代の経験などから問題解決を聞くことが多い。このような個人の経験を直接聞くような形式だと、「人間関係→結局上手く行った」「ここが困難だった→結果こう解決した」と言う具合にある程度回答が絞られてくる。人によって差が生まれにくいのが難点。そもそも「自分って明るい人間なんだぜ!」見たいに普段言うか?どう考えても気持ち悪い質問が日本の面接には多い。

「バスの中にゴルフボールは何個入るの?」と言う問題を考えてみる

では上記のGIGAZINEの質問の一つであるgoogle「バスの中にゴルフボールは何個入るの?」と言った質問を自分なりに考えてみた。その方法の一つは「問題を幾つかの段階や手順に分けて考える」と言うことだ。

問題の切り分け

上記のゴルフボールの例なら「バスの容積÷ゴルフボール1個あたりの体積」を計算すれば良いはず。ここで、

  1. ゴルフボールの体積を求める
  2. バスの容積を求める
  3. 「バスの容積÷ゴルフボール1個あたりの体積」

と言うように一つの問題を複数の段階、側面に分けて考える。要は問題を切り分けて考える事が大切。こうなってくると「ゴルフボールなどの体積はどうやって求めるの?」と聞かれるだろう。ならば水に沈める。断面を積分して集める。インターネットからゴルフボールの寸法を調べるなどのアプローチを答えて行けばよい。この繰り返しで周囲と問題を解決していくように話を進めていけばよい。これはポケットモンスターの開発元である「ゲームフリーク」のホームページの、「遊び」考え方のヒント | 応募書類について | 採用情報 | GAME FREAKでも、ジャンケンのような遊びでも以下のように切り分けると考えやすく、発展させやすいと言うことが書かれている。


  1. グー、チョキ、パーの3つがある。
  2. 2人以上で行う。
  3. グーはチョキに強く、チョキはパーに強く、パーはグーに強い、

又理系の場合自分の研究内容そのものが聞かる事が多いが、題材に左右される所があるので、全く違う所から問題解決能力をアピールできるのは有り難い。このような会社で面接をすると、仮に落ちたとしても至らない所が分かり後につながりやすいと個人的に思う。むしろこういう議題は研究進捗状況などでの差が生まれることは無く、個人の能力が試せると言う利点もある。研究内容とそれ以外と言う風に2段階で分けてくれた方が、採用される側もやりやすいと思う。

googleは、どれくらいの能力ある人が欲しいのかはっきり明記している

googleの面接の魅力的な点はどれくらいの能力があるのか客観的に明記している点だ。ではどのような能力が問われているのだろうか?面接のヒントから抜粋すると


面接のヒント
  • Google興味をもった理由志望動機を説明できるようにしておいてください。
  • Googleサービスについて把握しておいてください (こちらを参照)。業務内容に関して質問する場合もあります
  • 希望する職種について説明できるようにしておいてください。
  • ソフトウェア エンジニアなど技術職の面接を受ける場合には、データ構造やアルゴリズムに関する質問にも回答できるようにしておいてください。コードを、実際にホワイトボードなどに書いて回答するようお願いすることもあります。
  • ソフトウェア エンジニアの面接を受ける場合には、次のウェブサイトをお試しになることをお勧めします: www.topcoder.com (初級および中級レベルの問題がお奨めです)
  • 履歴書、レジュメにご記入いただいた内容をご確認させていただく場合もあります。たとえば、主要なプログラミング言語として C++Java を記載された場合、この分野に関する質問をお伺いすることがあります。

と日本の場合だとメーカーの技術面接でこのような事を聞かれるのだが、聞く内容を書いておいてくれるのは嬉しい。又日本のSIer企業などと比較すれば凄く具体的に面接の内容が書かれている点が特徴。日本の場合「求める人物像」が書いてあるのだが、どの能力をどれだけと言うことは余り書かれてない。これだと日本の会社の多くは「能力で採用してないのか?」と言うようになってしまう。正直基本的なコードの質問くらいは聞いてもおかしくないとは思うのだけど。

Powerpoint持ち込み面接も有りだと思う

Powerpointを作る際にもこの切り分け能力は問われる。例えばPowerpointのスライドだけ生徒に見せて、「これを説明してみろ」。又は話の流れを作っておいて、具体的な所は受験生に説明させるとか。例えばAと言う香水の現物とPowerpoint[どのような人に売る物なのか(年齢、性別)?どのような効果があるのか?(ピンクっぽい臭いなのでピンクの洋服に合う)、どれくらいの価格で売るのか?、どのように宣伝するか?]何処へ行っても何らかの説明することってあるし、そもそも大学ってレポートを通し、人に説明できる能力を身につける場と言っても過言では無いと思う。

こういう面接形式がはやれば、日本の大学生の就職対策も変わると思う。就職対策をするのはいいことなんだけど、その方向性が違うのがそもそもの問題だと思う。最後に、就職をされる方は自分を発揮出来る会社に就職されることを願いたい所だ。その方が自分の方にいい利益をもたらすとおもう次第だ。