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.
It would not be shocking to find out a cocky interviewer posed a brainteaser while leaving out a fundamental assumption, then judged an answer as incorrect because it violated that unspoken assumption - I can imagine Ballmer saying "no actually, you have to start with a guess of 50, everyone knows that."
I worked with a guy like this. He told me this story to impress me with how incisive he is. Instead it told me he is an egomaniac. His story went something like this, I don't recall the exact details:
"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.
Ah, the B type developer. Knows enough to find exciting and interesting problems but doesn’t know how to distinctly separate a type C (who can’t solve the problem at all) from a type A ( who knows the problem in and out and knows “it depends”). Not all that different to me from midlevel dev who learns about concurrency/metaprogramming/etc and starts using it as a tool for everything. Just enough to be dangerous.
Unless the interviewer has totally lost sight of the purpose of the interview, they’d recognise a candidate starting at an offset from 50 as an instant pass.
> you can select an initial guess that is offset from 50
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 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.
That approach would still leave you weak to always picking 1 or 100.
Without proof, I believe the optimal guessing strategy would perform equal (on average) for every number, to not give the opponent any standout choice (common for optimal strategies, but not always the case). If my math serves me right, that would be an average of log2(100) = 6.64 guesses for any number, which would make you lose 0.64$ on average.
I don't think you have to put your random offset all in the first guess either. Maybe you could random offset +/- 7 on the first guess, +/- 3 or 4 on the next, something like that.
The way forward is to make Ballmer pay with time for screwing with you, which gets us into geopolitics, and then using the resulting MAD dynamics to make the game fair again. That's how adults with keys to the nukes do it :).
The ultimate conclusion of which is likely that both parties will decay to picking the secret value/first guess randomly (although I'm not sure if the optimal distribution is perfectly flat?), which is also something that we can model.
I have not really studied this but maybe choosing the guess randomly when the number of possibilities is even is already enough to counter an adversarial opponent. Note that 50 is not the only 'optimal' guess in the beginning. 51 is just as good.
No it doesn't, it's quite clear that Ballmer can be choosing adversarially. The point is that even if Ballmer chooses randomly and the interviewee plays optimally given this, the game still has a negative expectation value, and that is enough to be sure the game is a loser for the interviewee.
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 think you did the math wrong. The expected value for the guesser is $0.20 if Ballmer chooses randomly. I think Balmer is saying that he can beat you if he chooses adversarially and you choose the expected initial guesses.
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.
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...
You have 31 positive payout guesses (1 $5, 2 $4, 4 $3, 8 $2 and 16 $1) leaving 69 other numbers with zero or negative payouts. You don't want to have gaps larger than three between your positive guesses, but there are 32 gaps for a total of 96 possibilities, or an excess of 27 over the numbers you need to cover.
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.
One can make the case for a perfectly rational adversary who always avoids picking paying numbers in anticipation of the opponent to exclude paying numbers successively in their guesses. When the game is played with perfectly rational characters the picker is doomed to select one specific number and thus you always make the maximum amount. There are some variations of the binary search but that can also be worked around. If they are not cheating, that is.
Other commenters are wrong in saying that the payout is different for an adversarial choice.
The crux of the payout derivation is: we can only cover 1 number in step 1, 2 in step 2, 4 in step 3, 8 in step 4, and so on. You can choose your initial number in binary search randomly, and as long as you meet the above condition is met (# of possible numbers covered in each step), payout should be same as 0.2
If I 'know' that my opponent is adversarial, then I might assume that he's not picking from the set of 100 possible numbers, but actually from a smaller set of 'adversarial' numbers, like the set that will always take 6 or 7 guesses using the naive binary search approach, and I can adjust my strategy accordingly.
> I'd be interested to see someone do the analysis of what the optimal random-offset-selection algorithm would be to counter trivial adversarial choice
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).
If Ballmer is being adversarial, he won’t pick the number at the start, and always win.
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.
Genuinely asking - not directly to OP of course, wasn’t this how people were playing the game when you were kids? Not as rigorous, but you intuitively try offsets to get lucky and find the number in fewer tries?
I'm not really married to this idea, but my first reaction is that to assume a random number would be an invalid assumption.
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.
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.
> they threw an obnoxious senior manager that kept interrupting me as I calmly answered the questions
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.
The way I read it:they inserted the manager as a litmus test AGAINST aggression / toxic culture. Kind of like when a psychology test is given, the __thing__ they're trying to measure is always one level removed / abstracted to avoid subjects gaming the system. I suppose deceptive practices in interviews don't bode well, but I could see the argument given the interviewee could be deceptive (something that this site complains about a lot with upper management / ChiefBullshittingOperatives etc.)
Personally, I don't like this kind of thinking that it's a failure of leadership first and foremost. Yes, of course leadership can both work proactively to prevent conflict, as well as try to minimize/react to situations. But, what about the conflicting people? Shouldn't they (in most situations), bear the most responsibility to not end up/turn a situation into a conflict? Sometimes I get afraid of comments that (in my interpretation) imply that basically everything bad that happens is the fault of leadership (management). To me that breeds a culture where ICs are taught to not own their situation, which I believe is very very dangerous (to everyone involved).
That SME guy sounds like an asshole, but I used to have an interview technique where I’d ask increasingly specific and low level questions about the candidates area of expertise until it got to the point where I’d be pretty confident they wouldn’t know the answer off the top of their head. I wasn’t adversarial or rude about it, I just wanted to find out if they were comfortable saying “I don’t know”, because not knowing something is an everyday part of technical work, but not being comfortable saying it can be big source of issues.
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.
I've been on the other side of that table. The interviewer stated in advance that the questions would get harder until I couldn't answer anymore, and that's OK because he wanted to see where my knowledge stopped. That clarity made it much more fun than stressful. I felt alright saying "I think the answer is X, but it could possibly be Y, and here's what the different implications would be".
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.
I always say I don’t know in interviews when I really don’t, rather than try to bluff. Some interviewers don’t like this though. As with the parent, perhaps that’s actually a good thing as you avoid having to work in a bad environment. Other times though, you may be being interviewed with a bad egg who you’ll never actually need to work with in the actual job.
My first interview at a FAANG company was so awesome. The interviewer said “I’m going to keep asking you questions till you can’t answer anymore. That way I learn the limit of your knowledge. If I can’t it’s because your knowledge in that area exceeds mine.”
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.
I remember some experiences where an interviewer thinks they are doing a deep reach for something they think should be an "I don't know", but it happens to be something you do know. Sometimes they think you're bullshitting or arrogant for this.
Judging people and getting an accurate read on people is hard. Often people are overconfident in their ability to do it.
Remember that you are talking to humans, they are flexible. You were being adversarial. If you could explain them in advance what you were trying to "read between lines", I'm pretty sure most/all of them would have changed their answers. So what you were supposing that was unfixable/permanent, apparently is fixable within 1 minute (of explanation).
I have the same idea in interviews. they need to be able to admit when they don't know or need help depending on the level. However I thought about it and I think the continuous "why" comes off as sort of childish or low effort. I didn't want to drive off people that reasonably didn't want to work in a place with a toxic culture. My solution was to ask a question that was specific to the workplace but technical so that it would require more information to solve. I looked for answers along the lines of:
- 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.
> because not knowing something is an everyday part of technical work, but not being comfortable saying it can be big source of issues.
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.
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.
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.
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.
Underrated comment. His point was to see how they approached the problem regardless of the answer, which is a much different criteria than having the right answer.
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.
This is greyed out, but I tend to agree with the sentiment that there’s a right way and a wrong way to approach these “EV” questions. OP was a bit harsh with the stupid comment, and for SWEs EV understanding is not usually a critical thing, but ultimately you’re being asked about the probability and the ability to make good decisions. Trading firms make use of this when hiring traders (most famously Jane Street and also SIG); The thinking is that if someone makes bad decisions with toy games, and their thought process is not analytical, they’re going to make for a bad trader, not making good decisions with millions of dollars on the line. A good example of something that would rule out a trader is: You can flip a coin, if you win you get $1m, if you lose you lose $1m. Would you play? The EV is zero, but the question is about bankroll management and disaster avoidance. As an individual the downside risk of a $1m loss (usually) significantly outweighs the upside of a $1m gain.
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.
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.
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".
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.
This is where binary search is not necessary. The admin could have just sent out unique messages, by making binary variations at 10 locations in the email (or ternary variations at 7 locations, or quaternary variations at 5 locations, etc.). E.g. choose 10 words, that can be replaced with a synonym, then generate 2^10 = 1024 unique messages to identify the leaker.
That's what we did in electronics too. There were kits with electronic circuits (this was back in the day with transistors.. and a bit more), where the teacher would introduce a fault somewhere. What we were taught was to start measuring signals in the middle, and then continue just like a binary search. This became so natural that when I ended up in programming in my first job I automatically did the same when searching for bugs in software. What surprised me was that other people didn't.
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.
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?
The "fundamental attribution error" is a bias where people attribute their own success to their inner abilities and other people success to external circumstances. (It's the reverse when thinking about failure)
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.
Just because it's one of my pet peeves, this is not what Dunning Kruger says. What it says is that people who are poorly skilled in a task will overestimate their skill and those highly skilled will underestimate, but not that the poorly skilled estimate themselves to be better than the highly skilled.
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.
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.
>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?
“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.
"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).
The candidate who can ask that is already better than the candidate that jumps straight into a solution. If I'm the interviewer, I'd be impressed with such a candidate.
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.
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.
Readit News
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.
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.
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.
Deleted Comment
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.
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.
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.
Judging people and getting an accurate read on people is hard. Often people are overconfident in their ability to do it.
- 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.
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
Dead Comment
Dunning–Kruger effect
https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_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.
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.
Dead Comment
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).
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.
Dead Comment