Steve Ballmer's incorrect binary search interview question

The article implies that the interviewee assumes that the number is being chosen randomly, when Ballmer could actually be choosing adversarially.

However, if the interviewee assumes that Ballmer is being adversarial, then you can pick a different value as your initial guess, which causes the probabilities to shift. Even the OP assumes that the interviewee will start guessing with 50, but, because of the way binary search works, you can select an initial guess that is offset from 50 (with a randomized offset each time) to defeat trivial adversarial attacks that attempt to game the heuristic, while still mostly reaping the benefits of binary search.

I'd be interested to see someone do the analysis of what the optimal random-offset-selection algorithm would be to counter trivial adversarial choices.

I recently interviewed for a senior level role for a complex domain (payments), this is an area I have more than a decade of experience. The interviews went flawlessly because I know payments inside out, not just in US but in UK and most EU jurisdictions. The funny bit is that the role being senior, influencing, soft communication skills and managing conflict are even more important than the subject matter expertise and I nailed those areas as well (they threw an obnoxious senior manager that kept interrupting me as I calmly answered the questions, the follow up was that my performance was a masterclass in handling conflict). The final round was with a business person who fancied himself the defacto subject matter expert and kept throwing trivia questions about payments. His plan was to go through as much trivia as he could until he could find something to justify a no. His last question (he literally stopped as soon as he got his way after this question), the question was, have you got personal experience working on real-time payments? I do, in more than one countries (US introduced this very recently as part of fednow), he pushed me about the fednow and obviously this is so new that I only have read the specifications and evaluated a few vendors to decide whether to build or buy. He used this as justification to make a negative reommendation, claiming I don't have real-time payments experience.

Honestly, I don't want to work in an environment like that, it was a large US bank and where their biggest problems are not product innovation or focusing on customer but production failures! An area I have rescued several large companies in, apart from payments expertise and made sure I communicated this. But sometimes you get lucky and don't have to find out the hard way that this place is not pleasant.

"Should you accept to play this game?"

Absolutely yes. I like games. The purpose of games is to have fun. This seems like a fun game for like the first $20, a sum I can afford to play a fun game for 10 minutes.

Then at the end, I get to say "I once lost $20 to Steve Balmer playing binary search", which is a fun sentence I can dine out on, and is worth more than $20 to me.

I feel like perhaps this is why MS under Balmer lost relevance. Too busy looking at the technical and not the human.

Slowly and for the span of many years I've come to realize that binary search is an amazing problem solving tool, specially on systems that are too big and complex to debug.

For example, recently a colleague had a problem with a rendering tool for Figma, of which we don't have the source code. The tool would take too long exporting a specific design. The team mate tried changing things randomly for days to no avail. Each try would take hours and sometimes crashed the browser.

The solution I gave him was to remove half of the elements and check how that affects the exporting time. Then keep repeating for the groups that still failed. In a matter of hours he found the element that caused a seemingly infinite loop.

Is there a name for the fallacy where you attribute your success in life to your own intelligence, and thus assume that you are smarter than everyone else, and that you therefor must be right about everything?

Sort of an opposite impostor syndrome?

I once had a colleague who had a favourite interview question, it had something to do with graph data structure and would always ask the question, many times candidate would reply and get rejected, strangely enough after a while all those candidates who replied got rejected. So we all gathered around him to work through what questions he was asking. We got to this question, and working with him on this question for a while we realised his solution to his own problem was wrong.

Turns out he was using this one question to reject people his whole career.

It was a humbling experience to all of us, to recheck everything before we asked questions. Most of the candidates you interview are perfect hires. Some times its you who is wrong.

As an interviewee my first question would be – are you going to play fair, and how can I verify it?

As with most interview questions, I’d expect this to be about how you think through it and show your work. If an interviewer asked this question and you found a mistake, that probably helps you get the job.

Some other interesting points here: Ballmer works hard to de-emphasize and diplomatically move away from discussing this exact question once it becomes clear that Chang's not approaching it by thinking explicitly about binary search and expected value.

Which is not surprising, because she's a professional journalist! It's amazing that Ballmer (like so many technical interviewers) is so pleased with this question that he couldn't help bringing it up, even though it's not really that relevant to Chang's question.

I really am curious about the Nash equilibrium solution. I assume that as a commenter has mentioned, for the guesser it involves returning random numbers near the binary search. But I’m curious if for the picker it involves a uniform or non uniform initial distribution?? I’m sure someone on HN knows/can explain?

It is also unclear if one has to keep playing. The expected value is very different if after the fifth guess one can thank Balmer for the opportunity and walk away.

How you end up hiring a mathematician while looking for a programmer.

This is a game with imperfect information, and the optimal strategy for each player is probably different from "pick any number at random" and "run off-the shelf binary search".

Didn't Steve Ballmer start off at MSFT essentially in a biz ops role, supporting execs when the company was super small? Interesting how he became technical as the company grew. Pretty rare.

I know no one asked for it, but here's a slightly simplified version of this script in Python:

    from itertools import count
    from statistics import mean

    INITIAL_PAYMENT = 5  # dollars paid if first guess is correct, minus 1 for each incorrect guess
    RANGE = range(1, 101)  # the range of numbers to guess from

    def simulate_guess(target):
        low = min(RANGE)
        high = max(RANGE)
        for bad_guesses in count():
            match guess := (low + high) // 2:
                case _ if guess < target:
                    low = guess + 1
                case _ if guess > target:
                    high = guess - 1
                case target:
                    return INITIAL_PAYMENT - bad_guesses

    average_payout = mean(map(simulate_guess, RANGE))
    print(f"\nExpected value per game: ${average_payout:0.2f}")

I believe you’d have to do a game theory analysis to actually get the answer (compute the mixed strategy that produces a Nash equilibrium). My intuition is that this yields <0 EV (because it’s already so small against a uniformly random strategy, which can’t be optimal) but I didn’t do the calculation.

> The question is "Should you accept to play this game?"

Absolutely. Best case I can tell everyone I beat Steve Ballmer in a bet. Worst case I tell him to take his winning dollars out my first paycheck...

I'm so glad I've managed my career such that I've never had to answer bullshit interview questions like this. The only purpose of these is to stroke the asker's ego, they tell you nothing at all about the candidate. What a waste of time.

I believe what Ballmer wanted to hear are clarifying questions.

Eg. Can I stop at any time? If yes, I will stop before I go into the negative. If I cannot stop but must continue the game until I guessed the right number, I will most likely lose money. Then go into a simple computation of XY terms where X is the probability and Y is the payout or loss for maybe a dozen terms.

Given that the number is not being picked randomly, this is more a game theory problem than a software problem.

Another stupid gotcha:

Ballmer states the question as "I'm thinking of a number between 1 and 100." He does not state that the number is an integer. If he's thinking of anything other than an integer, you're unlikely to be successful in finding it via binary search.

Is it really wrong though? In this case maybe you could game the system.

What if you combine binary search and game theory?(knowing that he’s trying to beat me and that binary search is my best strategy I have information reducing the randomness of the selection. I know Ballmer is going to choose worst case numbers like 58)

begin with binary search to narrow down the range, then within the range guess the binary search worst case answers. It’s still not guaranteed to win, but might be fun for the chance of taking his money.

Although leading by telling him that the worst case for the optimal algorithm of binary search on n=100 also gets you the job at Microsoft which is worth more than the two bucks you might earn playing the game.

This write-up makes the erroneous assumption that he's choosing randomly. He himself says, in this same write-up, that he's choosing adversarially.

Nice write-up anyway, and yes, Ballmer is wrong.

Title is wrong in implying Balmer is incorrect and the article shows that the title is wrong. If clickbait is misleading, then this is worse than clickbait, no?

> Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you...

The article goes on to show that there are numbers where a binary search always has the guesser paying $1

How come their software is so shit if they are so good at coming up with clever interview questions?

The best interview that I ever had was one in which the dude wore a fedora and we white-boarded. And yes we talked about algorithms. But I got the sense that he didn’t care if I knew any particular thing per se so much as was trying to figure out if I would be a fun person to jam with on hard problems.

Deep down we all know what programming, was supposed to be about, which is when you drop the ego and channel your childlike creative curiosity to create something you love, or to find like truth. People who know how to reliably find this state and enjoy it will become an “intelligent” person regardless of their original IQ. When I hire a full time role now, I look for people who are best able to channel this in the context of our team and our mission.

The problems come in when the creative output of the programming is being managed in a capitalistic system. If you take capital with the plans to build something and make money, then you have an entirely new set of constraints. You committed to a deadline so now you lose the ability to say “no”. Most programmers hate scrum/agile with a passion because these processes are basically the manifestation between the conflicts and misunderstandings that happen between shareholders and creators.

Nice, you played the game and you earned $0.20 [twenty cents]. Definitely a bad choice. But then you got viral on HN, and made good on your investment.

about the probabilities: say Steve's number is 59. I say 50, Steve says higher, so there are just 50 numbers left and the new probability is 1/50, I say 75, Steve says lower, so the probability is 1/24 (otherwise it would be 1/25), and so on

I wrote similar code to show that as long as you choose your starting number randomly you will have positive EV. Not sure how they kept using this interview question without realizing this.

https://x.com/sampullara/status/1810088483425558630

Disappointing to see the Nash equilibrium missing from the analysis.

The (TV) interview is kind of funny because the journalist asks him, after he goes through the idiotic song and dance of this brain teaser: "so what did you learn about me?" This is actually a very insightful question. What did you learn, Mr Ballmer?

To which he literally has no answer: "I learned you need to step back and really ask if you're going to make money on this thing".. uh, okay Steve. Cool. Thanks for your contribution to possibly the worst technical hiring practices in just about any professional field. The technicals are less interesting than seeing even he himself has no real justification for this kind of intellectual hazing.

If Ballmer asks me this question then I would obviously take it - expecting and hoping to lose. I would then guess the worst possible answers just so I’ll have a story to tell my grandkids how a billionaire fleeced me out of a few bucks while deciding the trajectory of my career. /s

I have opened the article in question. I have NOT worked through the technical problem, the complications and interpretation surrounding Ballmer, nor have I digested the contention being presented. I am capable of these things but I am on the clock and I do not value performing the work required for this particular article.

With that said, I wanted to share the following. Perhaps it will spur discussion.

Our leadership -- whether in our professional circumstances, in our sovereign and communal circumstances, or in our choice to lead ourselves; perhaps it is in these leaders that a view, or a decision, or a proclamation -- perhaps it is in these impulses that the world is changed.

Can you assign truth to an impulse? Is it a communication for consideration? Is it a demand for compliance?

I assert that you can do so. The words were spoken. Thus, the impulse was true.

If you desire to do so, please consider.