「ジャンプするすべてのものは、おおよそ同じ高さにジャンプする .. 体のどこにも故障がなければ、あなたは高さにして75センチ前後ジャンプできる。言い換えれば、重心をどれだけ高く持ち上げられるかということだ。馬、ウサギ、カエル、バッタ、ノミについても、75センチの跳躍力があると言っても的外れではない」
この文章は、googleの面接に実際にあった「あなたの身体がコイン大に縮んでミキサーのなかに放り込まれました。60秒後にミキサーの刃が回転を始めるとしたら、あなたはどうしますか？」という質問の正解「ジャンプして逃げる」の根拠となるものである。
「草の上に落とした卵はたいてい割れないのだ － どんなに高いところから落としても。 .. デイリー・エクスプレス紙は型飛行機を借り、時速240キロメートルで飛行しながら60個の卵を芝生の上に投下した。およそ60パーセントの卵が無傷だった」
この文章は、下記のgoogle面接質問と、回答を導くのに用いられる卵アルゴリズムの話に続く。
「あなたは100階建てのビルのどの階が『卵を落としても割れない』階かを調べる必要があります。あなたの手元にはまったく同じ性質の卵2つがあり、2つとも割ってしまってかまいません。あなたは卵を最大で何回落とせばよいでしょう？」
最初に思いつくアルゴリズムは下記のものである(「のんびりアルゴリズム」)。
・卵を手に持って、1階から落とす。割れなければ2階から落とし、それでも割れなければ3階から落とす。
この方法では、どの階が『卵を落としても割れない』階かを知ることが出来るが、最大で何回落とせばわかるかを特定することが出来ない。つまり、面接官の質問に応えることができない。
正解は ..
・ひとつめを何階から落とせば、それが割れたとしても、割れなかったとしても残りのひとつで答えにたどり着けるかを考えます。
・例えばひとつめを10階から落としたとして、
割れたら→「のんびりアルゴリズム」を採用して、1階から順に試してみればかならず答えにたどり着く。
割れなかったら→それでは思い切って20階まで登って落としてみると仮定します。そこでももし割れなかったら、30階。割れたところで「のんびりアルゴリズム」に切り替える。しかしこのやりかたでは、
最大トライ数を求めることはできません。
・こう考えてみます。
トライ数を仮に10回までとします(この、一見意味のない仮定がキーポイント)。そうすれば、ひとつめを10階から落として割ってしまった場合、許された残りのトライ回数9回で、1～9階を(低い方から)順に試せるから。さらに、ひとつめが10階から落としても割れなかった場合、次に試すべき階は20階ではありません。なぜなら、その時点で残されたトライ回数は9回に減っているから。つまり、次に試すべき階は19階になります。
・しかし.. このやりかたで100階までカバーできるのか？確認のために計算してみます。
10+9+8+7+6+5+4+3+2+1＝11×5＝55
残念ながら、55階までしかカバー出来ません。
・では何トライまで許されれば(最後の最後にふたつめが割れるという、最大ロスの場合でも)100階までカバーできるのか？最初に落としてみる階数と最大トライ数を同じ自然数Nとします。
N+(N-1)+(N-2)+(N-3)+(N-4)+(N-5)+ .. +3+2+1≧100
この式を解きます。
(N+1)×N÷2≧100
(N+1)×N≧200
Nの2乗+N≧200
いくつか数字を入れてみて..
N＝13だと13×13+13＝182、
N＝14だと14×14+14＝210。
求めるべき自然数Nは、14だということがわります。
・なにを導き出したかというと..
「ひとつめは、14階から落とす。もし割れたら『のんびりアルゴリズム』に切り替えて1階から順に落としてみる。この場合の最大トライ数は14回。もし最初のトライで割れなければ、次は14に13を足して27階から落としてみる。割れれば11階から『のんびりアルゴリズム』、割れなければ14+13+12＝39階からトライ。この方法ならトライ数が14回を越えることはなく、しかも答えにたどり着く前に卵をふたつとも割ってしまうことはありません」
「コンピューターの性能がいかに素晴らしくなっても指示を出すのは人間」というコトバがもうわたしがコドモのころから言われています。現代は「指示」が洗練されていることがなによりも求められる時代。アルゴリズムとは、ここでいう「指示」のこと。洗練された最適アルゴリズムにまっすぐたどり着くアタマの使い方を備えているかどうかをみる面接の話です。
ghostwriter
