Steve Ballmer's incorrect binary search interview question

Original Article ↗ Hacker News Discussion ↗

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.