スティーブ・バルマーの誤った二分探索（Binary Search）面接質問
(blog.jgc.org)- Microsoftの面接パズルとして紹介された数当てゲームは、二分探索と期待値を問うものだが、数字をランダムに選ぶという条件では「参加者に不利だ」という結論は誤り
- ルールは1〜100の間の数字をヒントで絞り込んで当てる方式で、当てるまでの推測回数が増えるほど$5から始まる報酬が減り、後半では参加者がお金を払う
- Ballmerが意図的に難しい数字を選べるという指摘は正しく、二分探索戦略でも特定の37個の数字は7回目になってようやく見つかるため、参加者が**$1を支払う**
- 数字がランダムなら、Perlコードでも確率計算でもゲームの期待値は$0.20となり、参加者に正の期待値を与える
- $0報酬の区間がなく、6回目の推測からすぐ参加者がお金を払うルールだったなら、期待値は**-$0.49**となり、Ballmerの結論と一致する
数当てパズルのルール
- Steve Ballmerは短い動画で、Microsoftの面接候補者に出したというパズルを紹介した
- 1人が1から100までの数字を思い浮かべ、応募者は推測するたびに「高い」または「低い」というヒントを受けて範囲を絞る
- 報酬は当てた推測回数によって変わる
- 1回目の推測: $5
- 2回目: $4
- 3回目: $3
- 4回目: $2
- 5回目: $1
- 6回目: $0
- 7回目: 参加者が$1支払う
- 8回目: 参加者が$2支払う
- 9回目: 参加者が$3支払う
- 核心となる質問は「このゲームを受けるべきか？」である
- Ballmerの結論は「No」で、その理由は2つだった
- 自分が最も当てにくい数字を選べる
- 自分がランダムに数字を選んだとしても期待値が負なので、参加者がBallmerにお金を払うことになる
Ballmerが正しかった部分: 敵対的に数字を選べる
- Ballmerが難しい数字を選べるという1つ目の理由は正しい
- 数字をランダムに選ぶという条件では、二分探索戦略が最適である
- 二分探索を使っても、Ballmerが特定の数字を選ぶと参加者は$1を支払うことになる
- 該当する数字は2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98, 100である
- 残りの数字では$0を受け取るか、正の報酬を受け取る
- $0になる数字は1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95, 99である
- それ以外の数字では、参加者がBallmerのお金の一部を受け取る
数字59の例
- Ballmerは動画で59を選んだ
- 二分探索戦略なら、50, 75, 62, 56, 59の順で5回で見つけられる
- この場合、インタビュアーのEmily Changは**$1を受け取る**
- Emily Changの実際の推測は50, 75, 60, 55, 57, 58, 59で、二分探索の5ステップの解法にかなり近かった
ランダム選択なら期待値は正
- Ballmerが数字をランダムに選ぶと仮定すると、期待値が負という結論は誤りである
- Perlコードは、1〜100の各数字について二分探索で何回で見つかるかを計算し、報酬を合計して平均を出す
- 計算結果、このゲームの期待値は**$0.20**である
- 同じ結果は確率の観点からも確認できる
- 1回目の推測で50を選び、成功確率は1/100、報酬は$5
- 2回目の推測で25または75を選び、成功確率は2/100、報酬は$4
- 3回目の推測で12, 37, 62, 88を選び、成功確率は4/100、報酬は$3
- 4回目の推測で6, 18, 31, 43, 56, 68, 81, 94を選び、成功確率は8/100、報酬は$2
- その後も同じ方式で続く
- 期待値の式は
5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100で、結果は0.2である - 最後の
-1 * 37/100の項は、二分探索の末端に到達した後に残る可能性のある数字を表す
エラーが起きた可能性のある箇所
- 1つの可能性は、Ballmerが**$0報酬の区間**を意図していなかったことだ
- ルールが「$5, $4, $3, $2, $1、その次は参加者が$1, $2, $3を支払う」だったなら、期待値は**-$0.49**になる
- この変形では、Ballmerの「期待値が負」という結論と一致する
1件のコメント
Hacker News のコメント
記事は、面接を受ける側が数字はランダムに選ばれると仮定していることを示唆しているが、実際には Ballmer が敵対的に選ぶ可能性もある
ただし、面接を受ける側が Ballmer の敵対的な選択を想定するなら、最初の推測値を変えることで確率を変えられる。原文の筆者も 50 から始めると見ているが、二分探索の性質上、50 から外れた初期値を毎回ランダムなオフセットで選べば、ヒューリスティックを狙った単純な敵対的攻撃を防ぎつつ、二分探索の利点はほとんど得られる
こうした単純な敵対的選択に対応する最適なランダムオフセット選択アルゴリズムの分析を見てみたい
Ballmer が「違います、最初の推測は 50 から始めるべきです。みんなそう知っていますよね」と言う姿が想像できる
つまり、最初の推測の両側に最大 64 個ずつあればよい。述べられているように、このオフセットをランダムに選べば、二分探索の隙を突く大半の敵対的な例は無力化され、場合によっては敵対的選択の利点そのものも消せるかもしれない。ただし、その場合はオフセットに合わせた分布が必要になる可能性もある
私もそういう分析を見てみたい
核心は、Ballmer がランダムに選び、面接を受ける側がそれに対して最適にプレイしても、ゲームの期待値は依然としてマイナスだということで、それだけでも面接を受ける側に不利なゲームだと確信できる
記事は「では実際の期待値はいくらなのか」という、より難しい問いには答えていない。だが、面接を受ける側が最初の推測を 40〜60 の間でランダムに選んでからそこで二分探索を行うなら、Ballmer が最初の数字をランダムに選ぶ場合より、特に有利になりにくいように見える
シミュレーションが見つけたあるナッシュ均衡では、Ballmer 側は範囲の両端付近を混ぜて選ぶ。常に 1 や 100 というわけではないが、その周辺だ。Ballmer プレイヤーが 1 ラウンドあたり約 0.85〜1.00 ドルの期待値で勝つ結果になった
結果として、当てる側の戦略も二分探索を範囲の極端なところから始め、どちらかを当てることを期待する形になる。サッカーのペナルティキックでキッカーとゴールキーパーが互いに方向を選ぶのに似ている。ゴールキーパーは同じ側を選びたく、キッカーは反対側を望む。だが選択肢が 100 個あるので、ゴールが広すぎるような感じだ
今では、残りの選択を二分探索パターンに縛らなければ均衡は完全に変わり、プレイヤーの結果も改善されるのではないかと見ている。ただし各範囲ごとに戦略選択が生じるため、計算はずっと重くなる。そしてこれをやっていたせいで 2 時間仕事を避けてしまったので、よくはない。それでも二分探索の制約を外すとどうなるのかは気になる
最近、複雑なドメインである決済分野のシニア職の面接を受けた。この分野で10年以上働いてきた。
米国だけでなく英国とEUの大半の法域における決済を隅々まで知っていたので、面接は非の打ちどころなく進んだ。シニア職なので、テーマに関する専門性よりも影響力、円滑なコミュニケーション、対立の管理のほうが重要だったが、その部分もうまくこなせた。わざと絶えず話を遮る厄介なシニアマネージャーを同席させられ、後続のフィードバックでは、対立処理のマスタークラスだったという内容だった。
最終ラウンドは、自分を事実上のドメイン専門家だと思っているビジネス担当者と行われ、彼は決済に関する雑学質問を延々と投げてきた。できるだけ多くの雑学をなぞって、却下する根拠を1つ見つけようという計画のように見えた。
最後の質問は、リアルタイム決済を実際にやった経験があるかというものだった。私は複数の国で経験があった。米国のFedNowは導入がごく最近だったので、仕様を読み、構築するか購入するか判断するためにいくつかのベンダーを評価した程度だった。彼はそれを根拠に、リアルタイム決済の経験がないとして不採用を推薦した。
正直、そんな環境で働きたいとは思わない。米国の大手銀行で、最大の問題は製品イノベーションや顧客重視ではなく、運用障害だった。決済の専門性とは別に、私が複数の大企業で救ってきた領域であり、その点もはっきり伝えた。それでも運がよければ、そういう場所が不快な場所だと苦労して知る必要はない。
会社に有害な文化があるだけでなく、その文化を受け入れているというシグナルに見える。そういう場所は対立を好む性向の人を引き寄せ、そういう人が十分に増えると彼らが文化を作る。
あまり頻繁には語られないが、対立はリーダーシップの失敗だ。非常に上位のリーダーが1人、指を鳴らしながら「お二人でこれを実現してください」と言うだけで、対立が解けることは多い。しかしリーダーシップが現場から離れすぎてチームを整列させられないか、競争という名のもとにチーム内の対立を体質的に擁護している。どちらにせよ、そういう場所は働くには地獄のようになり得る。
最終的には、候補者がその場で答えを知らないような地点まで行くやり方だった。敵対的に、あるいは無礼にやろうとしたわけではなく、「分かりません」と言えるかを見たかった。知らないことは技術職の日常的な一部だが、その言葉を気軽に言えないと大きな問題になり得る。
全般的に、最も有能な候補者ほど「分かりません」という答えを最も自然に言えた。防御的に出るのは常に危険信号だと見ていた。
有害な経営陣は、ずっと少ない報酬の社内社員よりも、過剰に高い報酬を取る外部コンサルタントやアドバイザーを好む。
完全に準備ができていて資格も十分なのに、プロセスが技術と経験の本当の評価ではなく雑学クイズのように感じられると、本当に苛立たしい。他の人たちが言うように、こうした振る舞いは有害な文化の明確なシグナルだ。
さらにおかしいのは、本来は正反対であるべきだという点だ。チームを拡大したり誰かを置き換えたりするなら、今いる誰よりも優れた人を探そうとすべきだ。
不採用にする理由を探すために些末な部分に難癖をつけたり、無関係な細部を掘り下げたりするなら、巨大な危険信号だ。イノベーションや実際の問題解決には関心がないという意味だ。私たちがすでに他社で解決してきた、終わりのない運用障害のような問題についても同じだ。
そういう状況では、時間を無駄にさせて申し訳ないと言って立ち去るのが最善だ。しかしその地域にその仕事があるなら、たわごとに耐えたくなるのも理解できる。それでも時には、その弾丸を避けたことが、形を変えた幸運になることもある。当時の私のように失職中で、お金が尽きかけていたとしてもそうだ。
答えが「農夫」になるまで祖先を問い詰めるようなものだ。
「このゲームを受けるべきか？」
もちろんだ。ゲームは好きだし、ゲームの目的は楽しむことだ。最初の20ドル程度なら、10分間楽しいゲームをする費用として許容できる。
終わった後には「Steve Ballmerと二分探索をして20ドル失ったことがある」と言えるし、これは食事の席で使えるいい一文なので、私にとっては20ドル以上の価値がある。
おそらくBallmer時代のMicrosoftが影響力を失った理由も、こういうところにあったのだと思う。技術的なことばかり見て、人間的な面をあまりにも見ていなかった。
面接でこう答えたなら、絶対に採用しなかっただろう。実際に一度、こういう候補者を面接したことがある。「これをどうしますか？」と聞くと、「それはやるべきではなく、別のことをすべきだと思います」と答えた。彼は採用されなかった。
何年もかけてゆっくり気づいたのだが、二分探索は、とくに大きすぎて複雑でデバッグが難しいシステムでは、驚くほど有効な問題解決ツールになる。
最近、同僚がソースコードのない Figma のレンダリングツールの問題に悩まされていた。特定のデザインを書き出すと非常に時間がかかり、同僚は何日もランダムにあれこれ変えてみたが、効果はなかった。1回試すのに数時間かかり、ときにはブラウザが落ちることもあった。
私が提案した解決策は、要素の半分を削除して、書き出し時間にどんな影響があるか確認することだった。その後、まだ失敗するグループに対して同じことを繰り返した。数時間で、事実上無限ループを引き起こしていた要素を突き止めた。
ワークステーションのようなエンドデバイスから一段離れるたびに、ネットワークの上位へ二段上がっていった。こうすると範囲を簡単に広げつつ、「ここまでは正常で、ここが壊れている」という地点を非常に素早く絞り込めた。
管理者は責任のある購読者を素早く特定するために二分探索を使い、メッセージのどこかに余分な空白文字を入れて、選択的に内容を変えていた。
コードの一部を削除して、それでも壊れるか確認し、さらに削除していく、という具合だった。
人生の成功を自分の知性のおかげだと考え、そのため自分は誰よりも賢く、あらゆることにおいて正しいと仮定してしまう誤りには名前があるのだろうか？
一種のインポスター症候群の反対側のようなものだ。
「自分は優れていて、すべてを知っている」という後半部分は、単なる昔ながらの嫌な性格と言えるかもしれない。
https://en.wikipedia.org/w/index.php?title=Luciferianism&old...
賢いなら自分が世界の守護者になるべきだ、という誘惑だ。自分の学びと究極の真理に基づく世界を作り、普通の人よりもそうした真理をより簡単かつ速く見つけられると考える誘惑である。そうして道徳に免許を与え、目的が手段を正当化するようになる。今している悪いことは、後で二倍の善として返ってくると信じる、といった具合だ。
根本的な帰属の誤りや Dunning-Kruger 効果もある。行動面では、幻想的優越感が道徳的ライセンシングと結びつき、大きな成功を収めた人ほどより大きなリスクを取る脱抑制効果も絡む。そのリスクには他人に悪影響を与えることも含まれる。
こうした効果がすべて、ある程度組み合わさっているように思う。必ずしも知性ではなく、少なくとも本人が認識している権力が問題のように見える。たとえば、自分は X が生まれつき他人より得意だと信じている人は、より大きな力を感じ、優越感を表したり他人を支配したりすることへの抑制が弱まる。
過去の栄光にしがみつき、もはや全盛期ではないことを理解せず、もう持っていない力を行使しようとする人を、私たちは皆見たことがある。私にとっては、それこそが本当のインポスター症候群の反対だ。自分自身と社会的力学への認識が、時代の変化に合わせて動いていない状態である。
自己愛性パーソナリティ障害
反社会性
以前、お気に入りの面接質問を持っている同僚がいた。グラフデータ構造に関する質問で、候補者たちが答えると次々に不採用になっていた。
不思議なことに、時間が経つにつれて、その質問に答えた候補者は全員不採用になっていた。そこで皆で集まり、彼がどんな質問をしているのかを見て、その質問を一緒に解いてみたところ、彼の独自解法が間違っていることに気づいた。
結局、彼はキャリアを通じてこの質問一つで人を不採用にしていたのだ。
私たち全員にとって謙虚になれる経験であり、質問を投げる前にすべてを再確認すべきだという教訓になった。面接を受ける候補者の大半は、十分に採用に値する人たちだ。ときには間違っているのはあなたのほうかもしれない。
ミスしたら即不採用なのか？ ほぼ全員をふるい落とせるほど完璧な応募者がそんなに多かったのだろうか？
面接を受ける側なら、最初の質問は「公正にやるつもりですか、そしてそれをどう検証できますか？」になるだろう。
「次に、有意な金額がかかっている場合は入力値を検証します。個人的にあなたを信用していないという意味ではなく、この状況そのものを信用しないものと見なします。これをどう検証できますか、それとも検証済みと仮定して進めることを望まれますか？」
良い質問だが、どう聞くかも重要だ。ソフトウェアエンジニアリングは純粋な工学だけではなく、コミュニケーションが非常に重要である。
ほとんどの面接質問と同じように、これはどう思考を展開し、解法の過程を見せるかを見る質問だと期待する。
面接官がこの質問を出し、あなたが誤りを見つけたなら、むしろ採用にプラスになる可能性がある。
ここには別の興味深い点もある。Ballmer は、Chang がこの質問に明示的に二分探索と期待値で取り組んでいないことが明らかになると、この具体的な質問の議論から離れようとして、かなり努力し、外交的に方向転換していた。
驚くことではない。彼女はプロの記者だ。驚きなのは、Ballmer が多くの技術面接官と同じようにこの質問を気に入りすぎていて、Chang の質問とはあまり関係がないのに、あえて持ち出さずにはいられなかったという点だ。
ナッシュ均衡の解が本当に気になる
あるコメントで言われていたように、当てる側は二分探索の近辺にあるランダムな数字を返す形になりそう。とはいえ、選ぶ側は一様な初期分布を使うのか、それとも非一様分布を使うのかが気になる。HNの誰かなら、きっと知っているか説明できるはず
5個の数字ゲームと100個の数字ゲームの間には、当然ながら大きな隔たりがある。選択肢の数が増えるほど最適混合戦略が安定する可能性もあるし、私の知る限りでは、ますます奇妙になっていく可能性もある。誰かが6個、7個などの数字ゲームをきちんと探索したら、ぜひ知らせてほしい
それ以外の戦略では、候補者には「だましの数字」を推測する戦略があり、Ballmerには「だましの数字を選ばない」戦略がある
候補者はBallmerにだましを使うよう強制できない