Steve Ballmer's incorrect binary search interview question
blog.jgc.org
blog.jgc.org
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 was interviewing a candidate who said he had experience programming on an IBM/370. So I asked him if you perform a character edit format instruction in EBCDIC mode with the leading zero specifier and the numeric value is too great to fit into the allocated field, after the instruction completes, what is the state of the program status word overflow field?" Then trounced the guy for not knowing. The thing is the guy asking the question happened to have worked on that instruction when he worked at Amdahl.
One thing to know is the IBM 360 and descendant family had a commercial instruction set option that, in a single instruction, could take a format value and generate a string output that followed some format specification, kind of like sprintf but with even more options.
"Is the computer operating on American electricity, or European?"
I think like 70% of interviews I ever had were like they were there to prove how smart they are and how stupid I am. I suppose most likely to make me feel stupid and accept lowball offer.
Often times, the "gotcha" part is just dumb and nonsensical, yet gives the interviewer(s) a sense of misguided (false) superiority, and wastes everyone's time. I would venture to say that 99% of the time it's complete un-indicative of how effective the candidate would be in the role.
Referring to my aforementioned bad interview - the question, after all the technical stuff had been cleared (this was for a junior frontend dev role) - they asked "imagine a car is broken and not running. how would you go about figuring out how to fix it?". Being someone whose brother and father enjoyed fixing cars, I asked every question about the problem with the car - how it was used, what sort of car it was, what the issue with the car was, what prior problems the car had, etc. I got a bunch of useless answers. After I exhausted all my questions, the interviewers told me I had failed. Why? One interview brought out a tiny hotwheels car with a missing wheel out of his pocket, and proclaimed to say "you didn't ask if it was a real car, it's a toy car, of fucking course it's not supposed to run like a real car!" while laughing hysterically. How on earth does that indicate if a junior frontend dev can do their job or not? Stupid.
The question was to estimate how many vacuum cleaners there were in the city we were in.
Fine, I did some estimation of how many vacuum cleaners per household and per office, across how many households and offices. Standard stuff.
Then the guy starts laughing and saying I'd failed because I didn't include discarded vacuum cleaners in landfills. Or the vacuum suction devices they put in your mouth at the dentist's office. And so forth. And then had to spend the next five minutes listening to him "teach me" how not to make assumptions. So I acted all polite and tried to fake "oh gosh thank you so much for enlightening me!"
Shockingly, I got the job, which required unanimous approval from all interviewers. Never met him again, and to this day I still have no idea whether this was supposed to be a test of estimation (which was easy to pass), a test of not making assumptions (which is dumb, but OK fine I failed), or a test of being appropriately professional and smiling in the face of complete bullshit (which I'd say I passed with flying colors).
I mean, in my professional life I've certainly had my fair share of customers and managers and coworkers who spout bullshit and you really do just have to lie with a smile and say "oh my gosh you're so right thank you for explaining that, I appreciate you so much!" Where you need to make them feel smart.
On the other hand, I just don't think he was thinking that far ahead.
I had a similar interview years ago - something like "how many windows are there on houses in our town?". Wasn't quite that, but I asked up front if "houses" meant just physical standalone houses, or if they meant living spaces, including apartments/dorms, etc. I got clarification, gave some estimate with some reasoning, and was then told I was the only person of the 8 they'd interviewed that had asked any clarifying question at all, which apparently impressed them enough to make an offer.
- Asked/did not ask clarifying questions
- Did/did not (or could not, on prompting) verbally walk through their reasoning
- Could/could not articulate which assumptions they felt were most important/why
Nothing about the actual content of the question itself, or if your answer was approximately correct (I usually did not know even the ballpark of the correct answer myself). I will say I did sometimes write down if candidates make comically bad assumptions. Like assuming the population of the USA was 1 Billion people. It's a fine line on what is "comically bad" but like, if you are interviewing for a startup of 20 people and you use $20B/year as the revenue assumption with no wink. That's a red flag. Lmao.
Is that comically bad? It's only like three times too much (if you're using the American, 10^9 billion), but we'd accept a much greater margin of error in some other assumptions (like in the classic 'how many Piano tuners are in the city', I think an assumption of 1-in-30 or 1-in-300 households having a piano (that would need tuning) all sound like they could be true!)
And if you’re interviewing, consider that for a decent proportion of people it may not be the country they live in (at least at the time you’re asking the question).
When you're in a real situation with a customer or user, you ask tons of questions. You use a lot of common sense to figure out what they really want, what's actually important, etc.
But often times these interview questions -- like how many vacuum cleaners in a city -- don't need any further questions asked. The idea that you'd count vacuum cleaners in landfills, or dental suction devices, is just silly. In real life, if someone wanted to know about the vacuum cleaners in landfills too, they'd tell you in the first place.
If an interviewer wants to see if someone can ask clarifying questions, they'd better come up with a scenario where it would make sense to ask them in a normal conversation. Scenarios that are genuinely ambiguous to anyone with common sense.
Otherwise interviews become this weird cargo-cult thing where you have to learn that interviewers present common-sense clear questions, but you have to ask silly clarification questions that you wouldn't in real life, just so somebody can check a box that you asked questions.
Assumption is mother of all fuckups.
I’ve seen customers wanting X and assuming that you should know that X comes with A and B because everyone in their business knows that. But you implement only X with A because you made your own assumptions and did not ask. So you missed the deadline and customer that’s it.
Playing devil's advocate, maybe a junior frontend dev that doesn't trust that they understand what someone is asking for and pushes back on bits that should be obvious will perform better (in some contexts?) than one that doesn't.
For a junior role in particular, though, it really doesn't seem like that should be the threshold and it sounds like it was delivered poorly on top of that.
The car example is just stupid. Could you image how idiotic you’d sound beginning by asking is it a real car? You’re basically accusing your interlocutor of operating in bad faith (which they were).
That interview question is basically, "We lied about an imaginary situation and were disappointed you failed to accuse us of lying mid-job interview."
Yeah, I think I agree. I was just responding to (what I saw as) sentiment that it was entirely unrelated to performance, which seems to overstate the case.
> Could you image how idiotic you’d sound beginning by asking is it a real car?
Tbh, "willing to sound like an idiot to double check assumptions" is probably something worth selecting for! I don't think that saves this question, though.
FWIW I would never ask these kinds of gotcha questions. I just give simple programming problems and talk through solutions with the candidates, and then throw in complications to the questions to make them more interesting and test more areas of the candidates knowledge and problem solving abilities. Yknow, like what happens on the job every day.
I am basically doing the same as I also interview people - but I also check the market from time to time as I am not company owner.
But I basically don't care about the offer if company pays guy much or not it is not my money and I only win if I get a smart, nice person who knows his job to work with.
Yes, that happens, and elsewhere she goes on about culture in tech.
One of the biggest red flags in an interview is if I ask a question and the person doesn't know how to say 'I don't know', because it suggests there's a big risk that if I assign them a task in their day-to-day work, they won't tell me if they feel unprepared to tackle it. That's a far bigger issue than not knowing that traceroute uses variable TTLs to figure out the timing along the route.
For what we know, the guy may well have been employing "test-taking strategies", and he may have been led down the garden path by the interviewer.
There's far too many posts in Rachel's blog where she goes on about "the one", who knows much better already, and here she channels the asshat that she complains about when she encounters him at work.
Each router checks its table for the destination, and if it doesn't know it, queries the next upstream router, its default route, the next hop. Each router likely ultimately informs you of the hand-off via a packet of some sort, and your then traceroute sends a ping/ICMP to each hop to learn how far away they are.
He maybe could've been pushed to expand on what he did know in more detail, but it seems like she just threw out SNMP as misleading bait, and he maybe mixed up ICMP and SNMP. She is right to call herself a troll, but wow, that's crazy to say she caught the guy in a lie of insanity.
When you think about it, the candidate isn't even that wrong. Back then, at university, a certain professor would explain the oral exam to the candidate at the beginning. He would explain that he would incrementally increase the difficulty and skip from area to area. The goal would be to find the limits of the student's knowledge, the student would walk away feeling terrible, and he, the professor, didn't enjoy the experience.
That's how it ought to be, but here? OK, candidate doesn't know ICMP well, next topic, no need to waste time and dig in.
Here's another unfavourable thought: some people with abusive childhoods react very badly to dominance displays, and here is Rachel engaging in just that. One wonders what had happened before.
Storytime! In a previous workplace a disagreement over fire safety with escalated into uncalled-for and unwelcome dominance behaviour from my supervisor. All attempts to deescalate were rebuffed, and now there is litigation from multiple plaintiffs, this person took out her sociopathic tendencies on many people. With a minimum of professional detachment or a HR department with a clue the peace would have been kept. (Yes, a few months later the fire marshal issued a code violation, as predicted.) You may not wish to live in that internet, but we live in a world where sociopaths are overrepresented in leadership positions.
Something rubs me here just the wrong way. Rachel complains about ageism and contempt for women in tech, and with good reason, and then she takes it out on an overenthusiastic candidate who can't read the room.
I assure you, I've met many people who treat their interviewees worse who are not sociopaths.
> Well, he guessed 69, sir, so I assumed he was doing some serious game theoretic calculations
Given that 7 guesses covers 128 numbers, you can offset by +/- 14 without actually affecting the "worst case" of the algorithm (i.e. provided you have at most 64 either side of your guess). As you say, randomly selecting this offset would neuter most adversarial examples (purposefully chosen to fall into the gaps of binary search) and would possibly completely remove the benefits from adversarial choice (though a tailored distribution on offset might be required there).
I'd be interested in such an analysis too.
I might be confused, but don't 7 guesses actually cover 255 numbers? I think you have to count all nodes in the search tree, not only the leafs, because you can get the correct number before reaching a leaf node.
Or more generally k guesses cover 2^(k+1)-1 numbers, e.g. with one guess you get the answers correct/high/low, which can cover 3 numbers)
Maybe there is a mistake in my thinking, because this would mean you can cover 127 numbers with 6 guesses so you could not lose the original game.
Edit: My mistake is that you still have to explicitly guess even if you know the precise answer already, so you cannot cover 3 numbers with 1 guess. This means 7 guesses cover 127 numbers.
You can also view it as a recurrence:
f(1) = 1
f(n) = 2*f(n - 1) + 1 = 2^n - 1
As the original article says, on average you can win $0.20. But that's indeed the upper bound if we speak of the adversarial number picking.
The game theory here is similar to another quiz "Guess 1/3 of the average".
You are really trying to guess how deep the other has thought about the problem, so you can tell which strategy they settled on, and then you adapt your strategy based on that. Of course, it's a loop.
The post never answers the question "so what is the real expectation value", which is a more difficult question. But I think if the interviewee chooses a number randomly from 40-60 as the first guess and does a binary search from there, Ballmer can't really improve on choosing his initial number randomly.
I agree that if you choose your first guess somewhat randomly in the 40-60 range (maybe not a uniform distribution though) Balmer would be forced to choose randomly and you would be back at a positive $0.20 EV. For example, you could flip 6 coins and add the number of heads, then flip another coin to decide whether you add or subtract the number of heads from 50 for your starting guess. But I think you would need to randomize your later guesses a bit also.
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...
It seems like a lot of possibilities and I think you can get away with a minimum gap size of one, but let's assume you do 5 3-gaps at 1, 25, 50, 75, and 100 and 2-gaps everywhere else. So start with 51, then 26 and 76. Then go up or down 12, then 6, then 3. If you have a gap of two you flip a coin, if a gap of three you pick the middle one.
Or if you have them write down the number and you think it has double-digits you could put your 4-gaps below 20. Start with 53 and go up or down 24, 12, 6, and 3 (unless it is below 20, then it is multiples of four.) 59 would pay you a dollar.
Your starting guess could be anywhere from 37 to 64 without paying out more than a dollar, but if you start with an extreme, then low odd numbers and high even numbers will have a negative payout. However, I think you can still randomize sufficiently starting with 38 and 63, e.g. 63-31-15-7-3-1.
https://gukov.dev/puzzles/math/2024/09/05/steve-ballmer-was-...
If you know your opponent picks a number uniformly from all numbers that lead to a maximum of guesses, the optimum strategy is a binary search between those numbers, making sure to pick one of those numbers at each turn.
The problem stays completely symmetric under this condition, so there would be two (maybe four due to edge conditions) optimal first guesses summing to 101.
In general, I think the trick still is a binary search where each guess splits the range of options in halves of equal expected/min/max cost (depending on whether you want to optimize for expected/min/max cost).
Of course you can set up the game such that Ballmer has to commit on a number at the start of the game (by sealing it in an envelope or whatever), but that wasn’t specified.
The scenario is framed as a zero sum game: one of us wins. The question is, "should you play?"
In order to answer, you need to be able to determine whether or not there is an optimal strategy that is generally successful.That should include both the assumption that Ballmer has chosen a number adversarial weighed against the random choice.
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.
This is a red flag. To me this signals that a company not only has a toxic culture, but embraces it. Such places attract personalities who love conflict and once there are enough people, they set the culture.
What doesn't get said often is that conflict is a failure of leadership. Often all it takes to resolve conflict is for one very senior leader to snap their fingers and say, "Guys, I want you two to make this happen". But what happens is that leadership is either far too disconnected from the ground to align their teams, or they constitutionally advocate conflict within their teams in the name of competitiveness. Either way, such places can be hell to work in.
I think a good comparison would be your romantic partner "testing" you by asking their friend to try to sleep with you and see if you try to go through with it. This is toxic, manipulative, sociopath level behavior.
Maybe I'm just interpreting your comment wrong :)
The candidates who were otherwise the most competent tended to be the most comfortable with the I don’t know answer. Getting defensive about it I always considered to be a red flag.
But for the luvagod, please state that up front. It wouldn't have been nearly so fun, or informational for the interviewer, if I'd felt like I was failing a quiz.
But this up-front approach of setting expectations seems like a better way to go.
What made it enjoyable was me knowing that I wasn't expected to know the gory details of how text editor internals work.
Edit: By honesty in interviews, I mean to a point. There’s some things you absolutely should lie about in interviews (if you’re confident you can get away with it). For instance “what’s your current salary” is a great question to lie about, that they really have no business asking anyway.
This framing has helped me ever since. It helped me emotionally to recognize that finding the limits of one’s knowledge is not a bad thing, it helped me get the job, it helped me interview people, it helped me hire people who knew more than me.
So it looks like all the top paying places interview this way.
Judging people and getting an accurate read on people is hard. Often people are overconfident in their ability to do it.
This is a false assumption. Especially generalizing the behavior in such an adversarial setup as a job interview to a regular day to day work/life.
> Telling people how I would want a good candidate to behave during an interview
You should tell them the rules of the game. The thing is, with interviews, there are already predefined assumptions, such as not knowing something takes a point from you, so people avoid this. In your case, you are altering these assumptions without disclosing it. So people might already had changed their behavior for the interview specifically - avoiding admitting not knowing something.
- I don't know - I don't have enough information based on the question - I would do it this way generally but this question requires employer specific information.
Not someone that just barreled forward and came up with a defacto answer as the solution. They had to give some sort of admission that they could not really solve the problem as is.
One time I had a candidate who didn’t not know about a single massively obscure thing I’d asked him. He was a DBA for a Chinese ISP that had more subscribers than we had total population in the markets we were operating in. That guy was probably the best hire I ever made. He was always in an incredibly genuine good mood, he was always happy to help everybody, and he’d help people learn how to solve problems rather than just doing the solving for them. Everybody on the team got smarter and more competent working with him, and he was so good at his job that he never even got behind on his own work due to helping other people all the time. I hope he’s still doing well now, before I left that company I managed to make sure he was being paid bucketloads of money (which wasn’t something he ever seemed to be seeking out independently, he was always just happy to come to work and do his job).
I'm honestly never afraid to say those words, if someone doesn't want to hire me because I said it, I dodged a bullet. I'll go where the devs and leads are sensible people.
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.
There: the same situation, pre-enacted by Steve Martin in Pink Panther: https://www.youtube.com/watch?v=mBwn7ycR7_Y. Probing one's ancestry until the answer is 'farmers'.
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.
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.
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.
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.
Sort of an opposite impostor syndrome?
For the second part of "I'm superior and know-it-all", I'd say it's good ol' jerk-ery?
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.
Narcissistic Personality Disorder
Sociopathy
Dunning–Kruger effect
From the wikipedia article you link:
> Among laypeople, the Dunning–Kruger effect is often misunderstood as the claim that people with low intelligence are more confident in their knowledge and skills than people with high intelligence.
The dunning krugger effect is widely regarded as the polar opposite of it:
- "If the Dunning-Kruger effect is being overconfident in one's knowledge or performance, its polar opposite is imposter syndrome or the feeling that one is undeserving of success. People who have imposter syndrome are plagued by self-doubts and constantly feel like frauds who will be unmasked any second." [1]
- "This is the opposite to the Dunning-Kruger effect. The Imposter Syndrome is a cognitive bias where someone is unable to acknowledge their own competence. Even when they may have multiple successes they struggle to attribute their success to internal factors." [2]
- "The opposite of the Peter Principle and Dunning-Kruger effect is the imposter syndrome. This is when smart, capable people underestimate their (...)" [3]
[1] https://www.psychologytoday.com/intl/basics/dunning-kruger-e....
[2] https://www.leedsforlearning.co.uk/Pages/Download/28541a2c-3....
[3] https://www.forbes.com/sites/jackkelly/2022/07/12/what-the-p...
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.
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?
They have to pretend to like they are working on things so special and hard that only the absolutely best would cut it.
“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.
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).
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.
It's not like in the day to day work you go around defining specifications for every tiny function - the default specification are clear from the work environment.
Let's say you had to implement a "find dups in this array" at work, you probably won't go around collecting requirements for that, so asking that in an interview and having the silly dance of "Oh, the interviewee didn't ask if the array fits in memory or not" is silly imo - and doesn't show anything other than whether the candidate memorized the need to ask that or not.
and like I said before, fuzzy specification are more suitable for the system/product design part, and can also be part of the coding part, but they shouldn't appear as some "gotcha".
I do say that, yes. Not necessarily with those words, but I tell interviewees that they are free to ask questions and in fact recommend that they do rather than they go start coding immediately and accidentaly solve the wrong problem. (Heck! Some people solve a harder problem than we intended to ask from them!)
> but they shouldn't appear as some "gotcha".
1000% agree with you on that.
But you never know if by asking the "right" question you'll jeopardize the entire interview problem. Some interviewers may have only prepared 75% of the problem and haven't went through all the posibilities. If you ask a question that may pose itself as a "treat" (e.g., making half the problem non-sense and therefore there's no need to implement it) your interviewer may simply consider you a no-go.
And it's not about malice, but simply that you may be better prepared than the interviewer and some times that leads to a no offer. I wouldn't mind working in a place like that, so I don't usually ask "too clever" questions.
Yeah. That can happen. As an interviewer i would tell the interviewee that they are right and it is because the example is a bit contrived and would ask them to pretend it still makes sense. If they are polite about the thing it would actually count in their favour.
But i understand it is a risk.
And frankly this is a needed skill. Candidates who automatically think about adversarial scenarios tend to write more defensive code, not to mention fewer vulnerabilities.
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.
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.
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.
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.
As the old saying can go, "It depends on what the meaning of 'can' can be."
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.
The math in this problem is rather simple, actually.
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.
> 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.
PS: Recruiters generally come from the same cloth as car sales and sports, so they're not usually going to be the sharpest pencils in the drawer.
Aren't you committing a similar mistake here, saying that recruiters can only recruit? At my former job one of the recruiters was an engineer for 20 years. He said he just wanted to do something different after all these years.
Almost everything is technical if you focus on it long enough, because almost everything is complicated.
This is because almost everything interacts with the real world, which is hellishly complicated and detailed.
> as either exclusively technical or nontechnical
This applies outside of tech or generally in any role e.g. if you're a backend engineer they assume you don't know frontend or if you're a marketing specialist you're not good at sales.
I never get it either. We're people not machines but most people have this assumption like we're a game character - you get a job / trait and that's it.
GT?
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.
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}")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...
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.
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.
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.
Nice write-up anyway, and yes, Ballmer is wrong.
> 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
But he also knows that you know that he could pick numbers that will be the most difficult... So could then pick one of the numbers that actually are guessable within 5 guesses to trick you.
But then you also know that he knows that you know that he could pick difficult numbers too.
I'm not entirely sure if this invalidates Ballmer's advantage, but I would be interested to know what the 'perfect' strategy would be for this game considering the meta-game.
If we accept cheating is allowed, we can also potentially accept other 'cheating' scenarios where the player repeatedly punches Ballmer in the face until he discloses the number, thus winning. Or where the player just refuses to pay at the end.
IMO the problem is only interesting if we assume any form of cheating isn't allowed.
Here, you can play the game with me. Higher. Lower. Higher. Higher. Lower. Correct. Six guesses, you owe me $1.
if I started off by guessing 50 twice you're cooked. or 50 and 52.
> secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer
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.
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.
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.
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.