Steve Ballmer's incorrect binary search interview question
Steve Ballmer’s famous binary-search brainteaser — “Should you play a game where you guess my number from 1 to 100, winning $5 on a first-try hit and losing $1 per extra guess?” — is being reexamined for both its math and its use in technical hiring. Commenters dissect whether his claim that the game has negative expected value is actually correct, especially once you factor in adversarial play, game theory, and optimal guessing strategies. The thread broadens into a critique of brainteaser-style interviews, arguing they often measure ego, trivia, and performance under contrived pressure more than real-world software engineering ability or collaborative skills.
Scope of the Question and Assumptions
- Central dispute: the TV question mixes probability, adversarial behavior, and interview meta-goals.
- Some note the article implicitly assumes the number is chosen uniformly at random; the TV clip explicitly allows adversarial choice.
- Several argue the article’s title overstates “incorrectness”: the original claim can be seen as about adversarial play and expected value, not pure binary search.
Random vs Adversarial Choice and Expected Value
- With a uniform random secret number and straightforward binary search, multiple commenters reproduce the result that the guesser has slightly positive expected value (around +$0.20).
- If the picker is adversarial but must commit to a number, standard “start at 50” binary search becomes exploitable: the picker avoids “easy” numbers.
- Counter-strategies discussed:
- Randomizing the initial guess within a band (e.g., 37–64) while preserving worst‑case depth.
- Randomizing offsets across later guesses.
- Several call for or sketch game-theoretic / Nash equilibrium analysis; consensus is that optimal strategies are mixed, not pure, and the true equilibrium EV is nontrivial and unresolved in the thread.
Cheating vs Adversarial Within the Rules
- Some point out that if the picker can change the number mid-game, they can always win; this makes the puzzle uninteresting unless precommitment (e.g., writing the number down) is enforced.
- Others insist the game is only interesting if “adversarial” means “worst-case choice within fixed rules,” not cheating.
Clarifying Questions and Trust
- Multiple commenters say a strong candidate would first clarify:
- Is the number an integer?
- Is it chosen randomly or adversarially?
- Is it precommitted and verifiable?
- Can the guesser stop early?
- This is framed as analogous to treating external inputs as untrusted in software design.
Interview and Brainteaser Culture
- Many criticize such puzzles as ego trips that poorly predict job performance, sharing stories of hostile or gotcha interviews.
- Others defend them if used to:
- Observe reasoning, communication, and ability to say “I don’t know.”
- Test comfort with ambiguity and clarifying requirements.
- There is broad agreement that delivery and framing matter far more than having the “correct” answer.
Broader Themes
- Discussion touches on:
- Over-pigeonholing people as “technical” vs “nontechnical.”
- Cognitive biases (Dunning–Kruger, narrative bias, attribution errors).
- Binary search as a powerful general debugging and diagnostics tool beyond coding.