Silicon Alley InsiderブログがGoogleの面接で出た難問を特集してましたよね。｢スクールバスにゴルフボールは何個入る？｣、｢8歳児に分かるようにデータベー スを3つの文章で説明せよ｣などです。
ギズもさっそく15題ご用意してみました。
1. 夫婦100組が住む村で夫が全員浮気した...妻はみんな他人の夫が浮気するとすぐ気づくのに、自分の夫の浮気には気づけない。村には不貞禁止の掟があり、夫の不倫を証明できた妻はその日のうちに夫を殺さなくてはならない。村の女は決してこの掟に背けないものとする。
ある日、村の女王がやって来て、この中に浮気をしてる夫が最低ひとりいると宣言した。さあ、どうなる？
読者Olivier Coudertさんからのベスト回答：この浮気夫の問題は、帰納法でよく出題されるものだね。 浮気夫が最低ひとりいると女全員が知った途端、あとはその後の成り行きから遡って事実関係がわかる。浮気夫がひとりしかいないなら、妻は犯人に誰も心当たりがないので夫が犯人とわかって、その日のうちに夫を殺すだろう。浮気夫がふたりだと、妻たちは犯人にひとり心当たりがあるが、自分の夫が犯人かどうかは1日置いて様子を見ないとわからない（浮気夫がひとりだけなら発表日のうちにひとり殺されるはずなので）。浮気夫が100人だと夫は全員しばらく命が安泰だが、99日後に妻100人全員が夫を殺す。職種： 製品マネジャー
（写真：symmetry_mind）
2. ある高速道路で30分以内に車が通る確率が0.95（95%）だとすると、10分以内に車が通る確率は？ （デフォルト確率は一定として）読者ruさんからのベスト回答：
この問題は、.95と言っても、たった1台じゃなく1台以上通る確率を指してるところが引っ掛けだね。30分以内に車が1台も通らない確率は0.05だから、10分以内に1台も通らない確率はその立方根。よって10分以内に車が通る確率は1引く｢それ｣、つまり~63%さ。
職種： 製品マネジャー
3. 夜間、ぐらぐらするロープの橋を渡ってキャンプに戻らなきゃならない人が4人いる...あいにく懐中電灯は1個しかなく、電池はあと17分しかもたない。橋は危険で懐中電灯無しには渡れないし、一度に2人の重量までしか支え切れない。各キャンパーとも歩くスピードはまちまちで、1分、2分、5分、ノロい人で10分かかる。 持ち時間17分で全員橋を渡るには、どうすればいい？
匿名読者からのベスト回答：1と2が渡って（2分経過）、1が戻り（3分経過）、5と10が渡って（13分経過）、2が戻り（15分経過）、1と2が渡る（17分）。これで全員無事だよ。
職種： 製品マネジャー
（写真：: Jule_Berlin）
4. 友人ひとりとパーティーに行ったら、出席者は自分と友人合わせて10人だった...友だちがこんな賭けを提案した。｢君と同じ誕生日の人を君が見つけたら君の勝ち。ひとり見つけるごとに1ドルあげる。君と同じ誕生日じゃない人を僕が見つけたら僕の勝ち。ひとり見つけるごとに2ドルもらう｣。この賭け、君なら乗るかな？
回答：季節的な出生率上昇は無視すると、誰かの誕生日が自分と同じ誕生日の確率は365分の1で、そうじゃない確率は365分の364。こんな賭けには乗らないよ。
職種： 製品マネジャー
5. 時計は3:15を指している。時針と分針がなす角度は？（ゼロじゃないからね！）読者Matt Beauchampさんからのベスト回答：
7.5度。分針が1度に刻む角度は6度（360度÷ 60分）。 時針は1時間かけて次の数字（この場合は3から4へ）に30度動く。3時ちょうどから4分の1時間経過してるので、時針は30度の4分の1動いてるんだよね...こたえは7.5度。
職種： 製品マネジャー
6. 1本の棒を折ったら3本になって三角形ができた。三角形が作れる確率を当てなさい出題では、棒が角で交わらなきゃならないとは言っていないので、答えは100%となるはず。どんなサイズのどんな棒でも3本あれば三角形はできるよね。
職種： 製品マネジャー
（写真：markhillary）
7. 南アでレイテンシの問題が発生した。原因を突き止めよ出題内容が極めて曖昧で、たったひとつの正解というのはない。面接を受ける人が｢レイテンシ｣という用語に精通しており、面白い問題に面白い解決策を思いつけるだけのイマジネーションを持ってるというところを示せたら、良回答。
職種：製品マネジャー
（写真：warrenski）
8. 2次元の面で、非同一線上の3地点から等距離になる線は何本引ける？読者Denisさんからのベスト回答：
3本。どれか2地点を選び、この線と平行になるよう、第3地点との中間にもう1本線を引く。これと同じことを考えうる全ての2地点で繰り返す。
職種： ソフトウェアエンジニア
（写真：Caveman 92223）
9. 2の64乗は？回答：
1.84467441 × 10の19乗（18446744073709551616）。 計算機も持たずに座って面接している状態でなければ、回答は一発でわかるんだけどね。
職種： ソフトウェアエンジニア
10. クローゼットはシャツが満杯で、1枚探すのもひと苦労だ。 どう整理したら簡単にシャツが引っ張り出せるだろう？回答はひとつではない。面接官は相手が問題解決でどんなイマジネーションとクリエイティビティを発揮できるか試しているのだ。読者｢Dude｣さんのベスト（？）回答：服の種類（HASHなど）で分け、さらに各種別ごとに2-3-4-TreeあるいはRedBlack Treeに仕分ける。
職種：ソフトウェアエンジニア
（写真：Brymo）
11. ティックタックトー（Tic Tac Toe）のゲームを渡され...ゲームの全経過とプレーヤーの名前をパスする機能を書くよう言われた。そのプレーヤーのゲーム勝敗結果を返す機能である。君ならこのゲームにはどのデータ構造を使うだろう？ 最初にアルゴリズムにそれを伝え、それからコードを書くものとする。（ゲームでは空白のスペースもあるので、その条件も考慮に入れたデータ構造にすること）
読者Dudeさんからのベスト回答：必要なデータ構造は、2次元アレイだ。この機能を呼び出し、6条件に照らして勝者がいるかどうかを確認する。6番目の条件は、残り余白の有無を判断するもの。 勝者がいるなら、｢X｣か｢O｣の文字にはプレーヤーが関連付けられている。この場合はフラッグが要る。勝者がいるなら、この呼び出し機能にゲーム終了のバリューを返す。いないなら、ゲーム継続。
職種：ソフトウェアエンジニア
（写真：frozenchipmunk）
12. 1兆個の数をソートするのにかかる時間は？ 正確に見積もる方法は思いつくだろうか。これも回答はひとつではない。面接を受ける人のクリエイティビティを試している。ギズが気に入ったのは読者2人から出されたシンプル回答。
マージソートでソーティングする。
O（1 000 000 000 000 Log 1 000 000 000 000） - アヴェレージ・ケース・シナリオ
O（1 000 000 000 000 Log 1 000 000 000 000）- ワースト・ケース・シナリオ
1秒で推定10億回の操作ができるので、答えは3000秒。
職種：ソフトウェアエンジニア
13. Froggerのゲームプレイ用のアルゴリズムをデザインし、そのソリューションのコードを書くとする...このゲームは、交通量の激しい道路で車にひかれずに横断できるようカエルを誘導するのが目的。車線はアレイで表現してもいい。N車線の道路という風にソリューションを一般化すると... って、この問題の解答はギズもがんばったけど、ひとつしか見つけられなかったよ。
Glassdoor.comにあるベスト回答次の車線に近づいてくる障害物の有無に応じて、いつ｢待機｣し、いつ次の車線に｢ジャンプ｣するか、そのタイミングを決める再帰アルゴリズムを書くのも、ひとつのアプローチ。
職種：ソフトウェアエンジニア
14. グーグルのソフトウェアエンジニア求人に届くレジュメは年間何件？これも採用希望者が、いかに問題をシンプルに捉え、クリエイティブに解決できるか見る能力診断テスト。
ギズのベスト回答：定量分析アナリスト採用希望者なら当然知ってることだけど、グーグルは2008年3400人採用した。うち75%（2550人）がエンジニアだとして、ハーバードのようにグーグルも応募者の3%しか採用しないとすると、3%が2550人だから総数は8万5000人。
職種：定量分析アナリスト
15. 数字のリストを渡された...リストの最後まできたら、最初に戻る循環リスト（環状リスト）がある。 このリストから最小数を探し出す最も効率の良いアルゴリズムを書け。また、言われた通りのナンバーをこのリストから探し出せ。リストの数字は常に増えるが、循環リストがどの数字で始まるかは分からない（例：38、40、55、89、6、13、20、23、36）
dudeさんからのベスト回答：当座のポインタを作り、ルートからスタートする（循環リストには大概、フロントとバックのポインターがある）。フロントとバックのどちらが大きいか調べ、フロントが大きかったら、それはリストの終わり＆始まりにいる証拠。フロント（バック？）が大きかったら、反対方向に転回し、数を比べてみる。ルートもポインタもリストのどこも指してなかったら、それはメモリで自分のデータが消失してしまった証拠だ。
職種： 定量分析アナリスト
The Business Insider（原文／satomi）
