13 ms·

Steve Ballmer's incorrect binary search interview question

264 points by jgrahamc 2y ago

more_corn 2y ago
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.
surfingdino 2y ago
How come their software is so shit if they are so good at coming up with clever interview questions?
eureka-belief 2y ago
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.
falcor84 2y ago
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}")
imagi 2y ago
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
kamaal 2y ago
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.
- carlmr 2y ago
  >strangely enough after a while all those candidates who replied got rejected. That also seems like a bad interview strategy. Make a mistake and you're out? Did you have so many perfect people to hire that you could just sort out almost everybody?
  - kamaal 2y ago
    Its the standard narrative at every place "We always hire the best". No body knows where the not-best people work at. They have to pretend to like they are working on things so special and hard that only the absolutely best would cut it.
deleted 2y ago
[deleted]
Eumenes 2y ago
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.
- re-thc 2y ago
  > Didn't Steve Ballmer start off at MSFT essentially in a biz ops role Yes, business manager. > Interesting how he became technical as the company grew. That's not clear from this. This shows he knew some concepts as part of managing different teams in the company.
  - hi-v-rocknroll 2y ago
    Ballmer was good at riding coat-tails of others as a supporting figure but eventually started running MSFT into the ground. He demanded to personally evaluate every M&A activity >$10M. No bueno.
- sudo_bang_bang 2y ago
  He graduated with a mathematics degree from Harvard so the concept of binary search would have likely been familiar to him. But you’re right, as far as I can tell, he never did any technical work like programming in his career.
  - ezero 2y ago
    Not only that, he was also better than Gates at math. From the acquired podcast episode on Microsoft: > Ben: He's gregarious. Anyone who's ever met Steve or seen a video of Steve, you are well aware that this man has a presence. But the thing that people don't know about him is he is so unbelievably analytical. Steve is the guy that outscored Bill Gates on the Putnam exam. source: https://www.acquired.fm/episodes/microsoft https://www.acquired.fm/episodes/microsoft
- throwaway984393 2y ago
  [dead]
toolz 2y ago
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
- kevincox 2y ago
  But if you know the number picker is going to choose these numbers you can optimize your algorithm.
  - paxys 2y ago
    How do you know that?
  - toolz 2y ago
    but you don't know. Only he knows that he's going to pick numbers the binary search will fail on and he states as much as his reason that you shouldn't play the game.
- michaelt 2y ago
  Also the number only exists in Ballmer's mind, so if he wanted to, he could change it to be unfavourable should you make a lucky guess. Here, you can play the game with me. Higher. Lower. Higher. Higher. Lower. Correct. Six guesses, you owe me $1.
  - dannyw 2y ago
    Yes, and a SWE should consider external inputs untrusted until proven otherwise.
  - pxx 2y ago
    your point is valid but you cannot have a static answer list. if I started off by guessing 50 twice you're cooked. or 50 and 52.
routerl 2y ago
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.
coldpie 2y ago
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.
- white_beach 2y ago
  correct answer
- dakiol 2y ago
  Same. I don't know if I have been lucky. I have worked with 6 companies in the past (startups, multinationals, consultancy companies, etc.) and I have never had to answer brain teasers.
dvt 2y ago
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.
- LudwigNagasena 2y ago
  He was being polite and understanding. They aren’t in a job interview setting, it’s not a correct frame to judge. But if it were, she would totally fail with that attitude of not thinking through the problem. That’s what his comment about stepping back meant.
  - twelve40 2y ago
    Well even if they were in an interview setting, how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work? They made so much money in the 90's that they could smash every other Ivy league candidate with a bat or make them do 500 jumping jacks, and still have people line up to interview.
    - LudwigNagasena 2y ago
      > how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work? Well, honestly, once to several times a week during backlog grooming, meetings with stakeholders and other similar stuff. I find it much easier to work with people with fast recall who can be confident and correct even under time pressure. Nobody wants to sit through many time-consuming meetings that end with “we will check that and get back to you later”. There is a succinct chess joke that summarises what being an expert means: a journalist asked Casablanca how many moves he thinks ahead. He replied, only one, but it is always the best one.
kibwen 2y ago
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.
- more_corn 2y ago
  Speaking of adversarial choices, the interviewee may wish to clarify that this number is an int and not a float :-p
- OneLessThing 2y ago
  Okay I did the simulation. I don't think this strategy actually works, but I initially thought it might like you did. One such nash equillibrium my sim found was having the Ballmer player mix between picking either end of the range (not always 1 or 100 but around those numbers). I have the Ballmer player winning with around $.85-$1.00 EV per round. The resulting player strategy was to also try to start their binary search at the extreme ends of the range and hope they guessed the right side. It's kind of like the soccer penalty kick dynamic between the shooter and goalie. Goalie wants to pick the same side, shooter wants opposite sides. But with 100 choices, the goal is too wide I think. I now think that not constraining the players remaining choices to follow binary search pattern would completely change the resulting equilibrium and improve the results for the player. But that would be more computationally demanding to calculate because there's a strategy choice for every range of choices. And also I've avoided work for 2 hours by working on this so that's not great haha. I _am_ curious what not constraining the player to binary search would do though...
  - gukoff 2y ago
cushpush 2y ago
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.
- Camus134 2y ago
  [dead]
throwaway984393 2y ago
[dead]
paxys 2y ago
As an interviewee my first question would be – are you going to play fair, and how can I verify it?
- bigbacaloa 2y ago
  [dead]
- dannyw 2y ago
  “As a SWE, I seek to understand important context first, before jumping to build or code. First, I’d like to ask if you’ll guess randomly and fairly, or adversarially?” “Secondly, when significant money is involved, I make sure to verify any inputs. I’m considering the situation, not you personally, untrusted. How can I verify it, or do you want me to proceed assuming that’s verified?” Those are great questions, but it’s also about how you ask it. SWE is not pure engineering. Communications is vitally important.
  - ibbih 2y ago
    wat
  - mupuff1234 2y ago
    "as you, my interviewer, are a capable SWE I assume you gave me all the context needed to solve the problem". The interviewing game of asking clarification questions is silly and should stop. In the system design portion I can understand it, but not when asked a direct technical question. It's perfectly fine to ask followup questions with added constraints or just directly say that the specification is fuzzy and needs to be clarified first, but having that dance around the basic specs in nonsense (as if you wouldn't know if you're dealing with a 10PB array or 1kb at work).
    - krisoft 2y ago
      > but not when asked a direct technical question. This is anything but a direct technical question though. > It's perfectly fine to ask followup questions with added constraints, but having the guessing game to figure out those constraints is nonsense. You say that. I say people being able to ask the right question is one of the most important skills to be a productive developer. So of course as an interviewer I want to know if they can do it. I don't know how it works where you are, but we don't have a big book of perfectly defined specifications for our work. I guess if we could get one of those that would improve our productivity. But until we obtain one we will keep testing candidates on their ability to ask questions.
seaprune 2y ago
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.
pbiggar 2y ago
"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.
- IshKebab 2y ago
  I don't know why you'd make this comment... I find it hard to believe you're actually stupid enough to not understand the implicit "(i.e. is your expected profit greater than 0)". If you answered like this in an interview I would definitely not give you the job. I did actually interview someone once who was like this - "How would you do this?" "Well you shouldn't do it. I think you should do this other thing.". He did not get the job.
  - xandrius 2y ago
    I would be glad not to given a job then, if that's how you react to someone taking the quiz and giving it its own twist. It's like interviewers don't understand the power dynamics going on during an interview: for the interviewer, this is just their job. Nothing will change for them whether they pass the candidate or not. This could be their 100th interview. On the other hand the interviewee is not paid to be there, they could be doing something else and they are stressed as who knows what kind of egocentric asshole might be interviewing them for a job they want. If I get a candidate who can make a fun and clear headed remark in such a tense situation, I would read that as them being comfortable with problems and with stress. I would move forward and ask further questions to see their thought process but rejecting someone out of a single question is ludicrous.
  - LudwigNagasena 2y ago
    I would be concerned if senior stuff wouldn’t speak up and bring up possible technical issues. That’s like half of their value.
dannyw 2y ago
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.
zeroonetwothree 2y ago
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.
krisoft 2y ago
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.
- tantalor 2y ago
  Good one! Reminds me of the viral video, goes something like "I'll pay you $20 if I can pour 2 cups of water on your head" and then only pour 1 cup and walk away.
  - netmare 2y ago
    IANAL, but they either have to honor the verbal contract (pour an additional cup AND pay $20) OR the contract is void and therefore they can be sued for assault. Of course, the "can" in "if I can" may be construed as "being able to", but that's up to the jury I guess.
    - gowld 2y ago
      Pouring more water isn't required, only the permission to pour more water is required. And that was granted in this scenario. As the old saying can go, "It depends on what the meaning of 'can' can be."
justusthane 2y ago
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?
- authorfly 2y ago
  A more unusual answer to this would be Luciferianism Temptations.. https://en.wikipedia.org/w/index.php?title=Luciferianism&oldid=1241180965 https://en.wikipedia.org/w/index.php?title=Luciferianism&old... The temptation that when you are smart you should become the guardian of the world, a world based on your learnings, your ultimate truths, truths you find easier and more quickly found than by the lay-person. Or so the temptation goes. It allows you to license your morality; the ends justify the means. What you are doing evilly now will be paid off twice-fold by the good it will lead to later. Right? There's the Fundamental Attribution Error and Dunning-Kruger effects too. And on behavior... Illusory Superiority combines with Moral Licensing (allowing yourself to be equally good and evil because you "match the two") and the dis-inhibition effect which people with greater success take more risks (including affecting other people negatively). I think these effects all sort of combine. It's not necessary intelligence but power, at least as perceived by the individual that seems to be a bit of an issue (e.g. the individual who thinks they are smarter at doing X innately feels more powerful and then has less inhibition about expressing their superiority and trying to dominate over others). We've all seen the person who ought to have moved on who hangs on to their former glory fail to understand they are not in prime condition and who tries to exert power they nolonger hold too.. to me that is the real opposite of imposter syndrome. it's when peoples perception of themself and social dynamics don't move with the times.
- tcgv 2y ago
  > an opposite impostor syndrome? Dunning–Kruger effect https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect
  - dustincoates 2y ago
alexey-salmin 2y ago
Disappointing to see the Nash equilibrium missing from the analysis.
- sobellian 2y ago
  For reasons given in the comments, both players probably choose a mixed strategy at equilibrium. If someone actually managed to find / prove a mixed strategy equilibrium for this game right there in the interview you probably couldn't go wrong hiring them on the spot.
jkaptur 2y ago
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.
eterevsky 2y ago
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".
- notfed 2y ago
  How is it imperfect information? Isn't each guess made openly?
  - eterevsky 2y ago
    Now I am not so sure, but the first player makes the move first (selects the number), then the second player makes their move without seeing the results of the first player's move. Meaning after the first move there is information hidden from the second player.
  - Closi 2y ago
    It's imperfect information because both players don't know the same information. Perfect information = Chess Imperfect information = Poker This fits into the latter category - if player 2 knew everything that player 1 knows, they would behave differently.
hennell 2y ago
> 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...
mekoka 2y ago
How you end up hiring a mathematician while looking for a programmer.
- slashdave 2y ago
  How you end up hiring a programmer while looking for a mathematician. The math in this problem is rather simple, actually.
- gowld 2y ago
  Ballmer and Gates were undergratuate mathematicians. It's not a bad strategy.
- jll29 2y ago
  This can be a big problem in teams that are homogeneous: All were hired using the same process, so all are maths/physics majors with good analytical skills but insufficient software engineering skills. What often happens maths/physics majors excel at programming the small, but cannot architect things in the large. As a friend once put it about one such person: "He can only do it as long as he can fit the whole problem in his head at once." It's great to have mathematicians and physicists in the team. But you for sure want a sufficient number of trained and experienced software engineers as well.
throwaway_1more 2y ago
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.
- rexreed 2y ago
  In an environment like that you'll be respected a lot more as a consultant and paid advisor, even if you provide generic and mediocre advice, than as an employee providing high quality expertise. Toxic management loves overpaid external consultants and advisors more than their own, much lesser paid internal staff.
- mianos 2y ago
  I've experienced something very similar in the same field. It's honestly frustrating when you're fully prepared and qualified, yet the process feels more like a trivia game than a genuine evaluation of your skills and experience. As others have pointed out, this kind of behaviour is a clear sign of a toxic culture. What's even more absurd is that it should be the exact opposite. If they're looking to grow their team or replace someone, they should be seeking out someone who's even better than anyone they currently have. When they nitpick or push for irrelevant details just to find a reason to say 'no,' it's a massive red flag. It shows they're not really interested in innovation or solving the real problems, like the endless production failures we've already helped other companies overcome. Honestly, in situations like that, the best thing you can do is apologise for wasting their time and walk away. But I get it when they have the job in your area, it's tempting to tolerate the nonsense. Still, it’s a good reminder that sometimes, dodging that bullet is actually a blessing in disguise, even though you are unemployed and running out of money, as I was at the time.
elromulous 2y ago
Given that the number is not being picked randomly, this is more a game theory problem than a software problem.
wolfi1 2y ago
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
spullara 2y ago
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 https://x.com/sampullara/status/1810088483425558630
- LudwigNagasena 2y ago
  I think they were using it just fine because they don’t say or in any way imply that the choice is random.
ckemere 2y ago
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?
- gowld 2y ago
  I don't see how Ballmer randomly guessing a number and candidate doing binary search would NOT be Nash Equilibrium. For anything else, the candidate has a strategy of "guessing a trick number", and Ballmer has a strategy of "not choosing a trick number". The candidate can't force Ballmer to try to be tricky.
  - quuxplusone 2y ago
    "Candidate always starts by guessing 50" can't possibly be part of a Nash equilibrium, since then Ballmer would never ever choose 50 as his secret number. (And indeed, he says as much in the linked video.) And if he'll never choose 50, then it's obviously silly for the candidate to waste a guess on it... and so on. Nash equilibria are usually (always?) located at mixed strategies.
- quuxplusone 2y ago
  I've taken a stab at analyzing the game for 3, 4, and 5 numbers here: https://quuxplusone.github.io/blog/2024/09/04/the-game-is-flawed/ https://quuxplusone.github.io/blog/2024/09/04/the-game-is-fl... There's obviously a huge gap between the 5-number game and the 100-number game; it's possible that the best mixed strategies settle down as the number of choices gets larger, or (for all I know) it's possible that the best mixed strategies get crazier and crazier. I'd love a ping if anyone does any real exploration of the 6-, 7-, etc.-number games.
readyplayernull 2y ago
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.
- authorfly 2y ago
  It shocks me that people don't think to do this more quickly generally (even intuitively).
- indrora 2y ago
  In the networking classes I took, we used binary search to determine where a problem was occurring, but with a slight twist: Each step away from the end device (e.g. workstation, etc.) take two steps upwards in the network. This broadened your scope easily but allowed for very fast refinement of "These are fine, but this is broken".
- roninorder 2y ago
  In the old days of DHTML when I was in my early teens this was the way I debugged very messy JS scripts (like multi-level menus). Remove some code - see if it still breaks, remove more, and so on.
- a57721 2y ago
  I recall a story about a private mailing list with ~1000 participants, where someone was leaking all the messages to the public. To quickly catch the responsible subscriber, the admin used binary search and selectively altered the messages by inserting an extra blank character somewhere.
  - 2y ago
rawgabbit 2y ago
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.
chihuahua 2y ago
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.
- tyilo 2y ago
  He also didn't state that the number is always in the set {59}, so you will always win 5 dollars.

264 points by jgrahamc 2y ago

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.

surfingdino 2y ago

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

eureka-belief 2y ago

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.

falcor84 2y ago

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}")

imagi 2y ago

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

kamaal 2y ago

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.

carlmr 2y ago
>strangely enough after a while all those candidates who replied got rejected. That also seems like a bad interview strategy. Make a mistake and you're out? Did you have so many perfect people to hire that you could just sort out almost everybody?
- kamaal 2y ago
  Its the standard narrative at every place "We always hire the best". No body knows where the not-best people work at. They have to pretend to like they are working on things so special and hard that only the absolutely best would cut it.

deleted 2y ago

[deleted]

Eumenes 2y ago

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.

re-thc 2y ago
> Didn't Steve Ballmer start off at MSFT essentially in a biz ops role Yes, business manager. > Interesting how he became technical as the company grew. That's not clear from this. This shows he knew some concepts as part of managing different teams in the company.
- hi-v-rocknroll 2y ago
  Ballmer was good at riding coat-tails of others as a supporting figure but eventually started running MSFT into the ground. He demanded to personally evaluate every M&A activity >$10M. No bueno.
sudo_bang_bang 2y ago
He graduated with a mathematics degree from Harvard so the concept of binary search would have likely been familiar to him. But you’re right, as far as I can tell, he never did any technical work like programming in his career.
- ezero 2y ago
  Not only that, he was also better than Gates at math. From the acquired podcast episode on Microsoft: > Ben: He's gregarious. Anyone who's ever met Steve or seen a video of Steve, you are well aware that this man has a presence. But the thing that people don't know about him is he is so unbelievably analytical. Steve is the guy that outscored Bill Gates on the Putnam exam. source: https://www.acquired.fm/episodes/microsoft https://www.acquired.fm/episodes/microsoft
throwaway984393 2y ago
[dead]

toolz 2y ago

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

kevincox 2y ago
But if you know the number picker is going to choose these numbers you can optimize your algorithm.
- paxys 2y ago
  How do you know that?
- toolz 2y ago
  but you don't know. Only he knows that he's going to pick numbers the binary search will fail on and he states as much as his reason that you shouldn't play the game.
michaelt 2y ago
Also the number only exists in Ballmer's mind, so if he wanted to, he could change it to be unfavourable should you make a lucky guess. Here, you can play the game with me. Higher. Lower. Higher. Higher. Lower. Correct. Six guesses, you owe me $1.
- dannyw 2y ago
  Yes, and a SWE should consider external inputs untrusted until proven otherwise.
- pxx 2y ago
  your point is valid but you cannot have a static answer list. if I started off by guessing 50 twice you're cooked. or 50 and 52.

routerl 2y ago

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.

coldpie 2y ago

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.

white_beach 2y ago
correct answer
dakiol 2y ago
Same. I don't know if I have been lucky. I have worked with 6 companies in the past (startups, multinationals, consultancy companies, etc.) and I have never had to answer brain teasers.

dvt 2y ago

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.

LudwigNagasena 2y ago
He was being polite and understanding. They aren’t in a job interview setting, it’s not a correct frame to judge. But if it were, she would totally fail with that attitude of not thinking through the problem. That’s what his comment about stepping back meant.
- twelve40 2y ago
  Well even if they were in an interview setting, how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work? They made so much money in the 90's that they could smash every other Ivy league candidate with a bat or make them do 500 jumping jacks, and still have people line up to interview.
  - LudwigNagasena 2y ago
    > how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work? Well, honestly, once to several times a week during backlog grooming, meetings with stakeholders and other similar stuff. I find it much easier to work with people with fast recall who can be confident and correct even under time pressure. Nobody wants to sit through many time-consuming meetings that end with “we will check that and get back to you later”. There is a succinct chess joke that summarises what being an expert means: a journalist asked Casablanca how many moves he thinks ahead. He replied, only one, but it is always the best one.

kibwen 2y ago

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.

more_corn 2y ago
Speaking of adversarial choices, the interviewee may wish to clarify that this number is an int and not a float :-p
OneLessThing 2y ago
Okay I did the simulation. I don't think this strategy actually works, but I initially thought it might like you did. One such nash equillibrium my sim found was having the Ballmer player mix between picking either end of the range (not always 1 or 100 but around those numbers). I have the Ballmer player winning with around $.85-$1.00 EV per round. The resulting player strategy was to also try to start their binary search at the extreme ends of the range and hope they guessed the right side. It's kind of like the soccer penalty kick dynamic between the shooter and goalie. Goalie wants to pick the same side, shooter wants opposite sides. But with 100 choices, the goal is too wide I think. I now think that not constraining the players remaining choices to follow binary search pattern would completely change the resulting equilibrium and improve the results for the player. But that would be more computationally demanding to calculate because there's a strategy choice for every range of choices. And also I've avoided work for 2 hours by working on this so that's not great haha. I _am_ curious what not constraining the player to binary search would do though...
- gukoff 2y ago

cushpush 2y ago

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.

Camus134 2y ago
[dead]

throwaway984393 2y ago

[dead]

paxys 2y ago

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

bigbacaloa 2y ago
[dead]
dannyw 2y ago
“As a SWE, I seek to understand important context first, before jumping to build or code. First, I’d like to ask if you’ll guess randomly and fairly, or adversarially?” “Secondly, when significant money is involved, I make sure to verify any inputs. I’m considering the situation, not you personally, untrusted. How can I verify it, or do you want me to proceed assuming that’s verified?” Those are great questions, but it’s also about how you ask it. SWE is not pure engineering. Communications is vitally important.
- ibbih 2y ago
  wat
- mupuff1234 2y ago
  "as you, my interviewer, are a capable SWE I assume you gave me all the context needed to solve the problem". The interviewing game of asking clarification questions is silly and should stop. In the system design portion I can understand it, but not when asked a direct technical question. It's perfectly fine to ask followup questions with added constraints or just directly say that the specification is fuzzy and needs to be clarified first, but having that dance around the basic specs in nonsense (as if you wouldn't know if you're dealing with a 10PB array or 1kb at work).
  - krisoft 2y ago
    > but not when asked a direct technical question. This is anything but a direct technical question though. > It's perfectly fine to ask followup questions with added constraints, but having the guessing game to figure out those constraints is nonsense. You say that. I say people being able to ask the right question is one of the most important skills to be a productive developer. So of course as an interviewer I want to know if they can do it. I don't know how it works where you are, but we don't have a big book of perfectly defined specifications for our work. I guess if we could get one of those that would improve our productivity. But until we obtain one we will keep testing candidates on their ability to ask questions.

seaprune 2y ago

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.

pbiggar 2y ago

"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.

IshKebab 2y ago
I don't know why you'd make this comment... I find it hard to believe you're actually stupid enough to not understand the implicit "(i.e. is your expected profit greater than 0)". If you answered like this in an interview I would definitely not give you the job. I did actually interview someone once who was like this - "How would you do this?" "Well you shouldn't do it. I think you should do this other thing.". He did not get the job.
- xandrius 2y ago
  I would be glad not to given a job then, if that's how you react to someone taking the quiz and giving it its own twist. It's like interviewers don't understand the power dynamics going on during an interview: for the interviewer, this is just their job. Nothing will change for them whether they pass the candidate or not. This could be their 100th interview. On the other hand the interviewee is not paid to be there, they could be doing something else and they are stressed as who knows what kind of egocentric asshole might be interviewing them for a job they want. If I get a candidate who can make a fun and clear headed remark in such a tense situation, I would read that as them being comfortable with problems and with stress. I would move forward and ask further questions to see their thought process but rejecting someone out of a single question is ludicrous.
- LudwigNagasena 2y ago
  I would be concerned if senior stuff wouldn’t speak up and bring up possible technical issues. That’s like half of their value.

dannyw 2y ago

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.

zeroonetwothree 2y ago

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.

krisoft 2y ago

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.

tantalor 2y ago
Good one! Reminds me of the viral video, goes something like "I'll pay you $20 if I can pour 2 cups of water on your head" and then only pour 1 cup and walk away.
- netmare 2y ago
  IANAL, but they either have to honor the verbal contract (pour an additional cup AND pay $20) OR the contract is void and therefore they can be sued for assault. Of course, the "can" in "if I can" may be construed as "being able to", but that's up to the jury I guess.
  - gowld 2y ago
    Pouring more water isn't required, only the permission to pour more water is required. And that was granted in this scenario. As the old saying can go, "It depends on what the meaning of 'can' can be."

justusthane 2y ago

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?

authorfly 2y ago
A more unusual answer to this would be Luciferianism Temptations.. https://en.wikipedia.org/w/index.php?title=Luciferianism&oldid=1241180965 https://en.wikipedia.org/w/index.php?title=Luciferianism&old... The temptation that when you are smart you should become the guardian of the world, a world based on your learnings, your ultimate truths, truths you find easier and more quickly found than by the lay-person. Or so the temptation goes. It allows you to license your morality; the ends justify the means. What you are doing evilly now will be paid off twice-fold by the good it will lead to later. Right? There's the Fundamental Attribution Error and Dunning-Kruger effects too. And on behavior... Illusory Superiority combines with Moral Licensing (allowing yourself to be equally good and evil because you "match the two") and the dis-inhibition effect which people with greater success take more risks (including affecting other people negatively). I think these effects all sort of combine. It's not necessary intelligence but power, at least as perceived by the individual that seems to be a bit of an issue (e.g. the individual who thinks they are smarter at doing X innately feels more powerful and then has less inhibition about expressing their superiority and trying to dominate over others). We've all seen the person who ought to have moved on who hangs on to their former glory fail to understand they are not in prime condition and who tries to exert power they nolonger hold too.. to me that is the real opposite of imposter syndrome. it's when peoples perception of themself and social dynamics don't move with the times.
tcgv 2y ago
> an opposite impostor syndrome? Dunning–Kruger effect https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect
- dustincoates 2y ago

alexey-salmin 2y ago

Disappointing to see the Nash equilibrium missing from the analysis.

sobellian 2y ago
For reasons given in the comments, both players probably choose a mixed strategy at equilibrium. If someone actually managed to find / prove a mixed strategy equilibrium for this game right there in the interview you probably couldn't go wrong hiring them on the spot.

jkaptur 2y ago

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.

eterevsky 2y ago

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".

notfed 2y ago
How is it imperfect information? Isn't each guess made openly?
- eterevsky 2y ago
  Now I am not so sure, but the first player makes the move first (selects the number), then the second player makes their move without seeing the results of the first player's move. Meaning after the first move there is information hidden from the second player.
- Closi 2y ago
  It's imperfect information because both players don't know the same information. Perfect information = Chess Imperfect information = Poker This fits into the latter category - if player 2 knew everything that player 1 knows, they would behave differently.

hennell 2y ago

> 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...

mekoka 2y ago

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

slashdave 2y ago
How you end up hiring a programmer while looking for a mathematician. The math in this problem is rather simple, actually.
gowld 2y ago
Ballmer and Gates were undergratuate mathematicians. It's not a bad strategy.
jll29 2y ago
This can be a big problem in teams that are homogeneous: All were hired using the same process, so all are maths/physics majors with good analytical skills but insufficient software engineering skills. What often happens maths/physics majors excel at programming the small, but cannot architect things in the large. As a friend once put it about one such person: "He can only do it as long as he can fit the whole problem in his head at once." It's great to have mathematicians and physicists in the team. But you for sure want a sufficient number of trained and experienced software engineers as well.

throwaway_1more 2y ago

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.

rexreed 2y ago
In an environment like that you'll be respected a lot more as a consultant and paid advisor, even if you provide generic and mediocre advice, than as an employee providing high quality expertise. Toxic management loves overpaid external consultants and advisors more than their own, much lesser paid internal staff.
mianos 2y ago
I've experienced something very similar in the same field. It's honestly frustrating when you're fully prepared and qualified, yet the process feels more like a trivia game than a genuine evaluation of your skills and experience. As others have pointed out, this kind of behaviour is a clear sign of a toxic culture. What's even more absurd is that it should be the exact opposite. If they're looking to grow their team or replace someone, they should be seeking out someone who's even better than anyone they currently have. When they nitpick or push for irrelevant details just to find a reason to say 'no,' it's a massive red flag. It shows they're not really interested in innovation or solving the real problems, like the endless production failures we've already helped other companies overcome. Honestly, in situations like that, the best thing you can do is apologise for wasting their time and walk away. But I get it when they have the job in your area, it's tempting to tolerate the nonsense. Still, it’s a good reminder that sometimes, dodging that bullet is actually a blessing in disguise, even though you are unemployed and running out of money, as I was at the time.

elromulous 2y ago

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

wolfi1 2y ago

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

spullara 2y ago

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 https://x.com/sampullara/status/1810088483425558630

LudwigNagasena 2y ago
I think they were using it just fine because they don’t say or in any way imply that the choice is random.

ckemere 2y ago

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?

gowld 2y ago
I don't see how Ballmer randomly guessing a number and candidate doing binary search would NOT be Nash Equilibrium. For anything else, the candidate has a strategy of "guessing a trick number", and Ballmer has a strategy of "not choosing a trick number". The candidate can't force Ballmer to try to be tricky.
- quuxplusone 2y ago
  "Candidate always starts by guessing 50" can't possibly be part of a Nash equilibrium, since then Ballmer would never ever choose 50 as his secret number. (And indeed, he says as much in the linked video.) And if he'll never choose 50, then it's obviously silly for the candidate to waste a guess on it... and so on. Nash equilibria are usually (always?) located at mixed strategies.
quuxplusone 2y ago
I've taken a stab at analyzing the game for 3, 4, and 5 numbers here: https://quuxplusone.github.io/blog/2024/09/04/the-game-is-flawed/ https://quuxplusone.github.io/blog/2024/09/04/the-game-is-fl... There's obviously a huge gap between the 5-number game and the 100-number game; it's possible that the best mixed strategies settle down as the number of choices gets larger, or (for all I know) it's possible that the best mixed strategies get crazier and crazier. I'd love a ping if anyone does any real exploration of the 6-, 7-, etc.-number games.

readyplayernull 2y ago

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.

authorfly 2y ago
It shocks me that people don't think to do this more quickly generally (even intuitively).
indrora 2y ago
In the networking classes I took, we used binary search to determine where a problem was occurring, but with a slight twist: Each step away from the end device (e.g. workstation, etc.) take two steps upwards in the network. This broadened your scope easily but allowed for very fast refinement of "These are fine, but this is broken".
roninorder 2y ago
In the old days of DHTML when I was in my early teens this was the way I debugged very messy JS scripts (like multi-level menus). Remove some code - see if it still breaks, remove more, and so on.
a57721 2y ago
I recall a story about a private mailing list with ~1000 participants, where someone was leaking all the messages to the public. To quickly catch the responsible subscriber, the admin used binary search and selectively altered the messages by inserting an extra blank character somewhere.
- 2y ago

rawgabbit 2y ago

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.

chihuahua 2y ago

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.

tyilo 2y ago
He also didn't state that the number is always in the set {59}, so you will always win 5 dollars.