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."
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.
What was the last time you were on the interview?
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.
One of the worst interviews I ever had was just like that.
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.
I had an interview at a major tech company with a similar thing, for a more managerial role.
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.
Is the landfill actually 'in' the city, or in a rural area outside the city limits?
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.
Yes, I have used questions like this before for junior roles and the notes for the interview were something like:
- 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.
Yeah, I think there's a possible pitfall with using this as an interview technique though.
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.
Well cannot agree really.
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.
Yeah I mean the vacuum landfill thing is stupid. The point was never to try to trip people up, there's no wrong answer (or question), just find out if they could recognize ambuiguity. "Let's try to estimate the amount of pet food sold each year in the USA." -> "Dogs and cats too?", "In terms of dollars or pounds of food?" type of stuff. This was for analyst roles - basically your whole job would be something similar to this where you're asked ambiguous questions and you need to translate that into a semi-rigorous analysis, infer intent, etc. I hate to say it but if you didn't realize that going into the interview, you were probably not a good fit as an analyst in the first place!
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!)
Totally my personal opinion, but not knowing the approximate population of the country you live in betrays a pretty serious lack of curiosity about the world. Obviously a judgement call on how far off is "far off", but it just gives a funny feeling, you know?
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.
I hear what you’re saying, but really, this is a stupid question and a waste of everyone’s time. Instead you could give a real big report that has insufficient information or that contains a red herring to an improper assumption. The interviewer could then measure if the candidate properly pushed back, exposed an improper assumption and asked relevant clarifying questions. Like one would do at the actual job exhibiting the characteristics the question purports to measure.
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).
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.
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.
Not just that, but the person said they did ask the interviewer what kind of car it was and what it was used for, at which point any reasonable person would explain it was a toy!
That interview question is basically, "We lied about an imaginary situation and were disappointed you failed to accuse us of lying mid-job interview."
Might be good as an exercise in a workshop on requirements gathering, as part of an interview absolutely stupid.
Great interview from a certain perspective. You knew for sure (if you had a choice) that you didn't want to work for this specific person.
That just feels like playing chess with a pigeon
Like this one: https://rachelbythebay.com/w/2011/07/27/ohreally/
Yes, that happens, and elsewhere she goes on about culture in tech.
Is the guy's response really that far off?
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.
Is the guy's response really that far off?
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.
Downvoted for jumping from legitimate criticism of her interview methodology to very personal and completely baseless accusations. This is not the internet I want to live in.
This is not the internet I want to live in
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 wasn't denying the existence of antisocial people, I was decrying the public shaming of someone you've never met as a victim of child abuse, and now also as a sociopath, based on only a small thing they wrote on the internet.
I assure you, I've met many people who treat their interviewees worse who are not sociopaths.
The stepwise increasing TTL is the fundamental mechanism that makes traceroute work. Any answer that omits this is so vacuously incomplete that it might as well be considered wrong.
fair enough, I guess the TTL exceeded response is how you learn about each hop
I strongly agree with the sibling comment that this is a perfectly valid interview question.
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.
The problem with "I don't know" is that it's really not culturally appropiate to say! Americans are supposed to be rugged, resourceful individualists and asking for help is frowned on because it shows weakness. Can't do that in an interview!
"I do not know" is not asking for help. It is a statement of fact.
I don’t doubt this happens but seems like a poor example. She effectively rooted out a bullshitter. No worries if you don’t know how a tool works, but just say I don’t know. That answer was nonsensical.
The purpose of an interview is not to root out a bullshitter but to find someone you can work with. If that guy doesn't know about TCP/IP, move on to the next topic. If the guy has poor attitude, be polite. Just don't waste time with making fun of the candidate, it does not reflect well on interviewer and company.
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.
It’s been a long long time since I was interviewed for a job, but I have conducted a lot of interviews since then and any signal that the candidate has engaged with the question and has interesting thoughts about it is a huge plus.
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.
Good for you, as you look for someone to work with, not someone to cut down their offer.
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.
Yea, they’re pointless. The amount of time someone spends on a truly difficult and important problem is maybe 0.1% of their job. And usually it’s better to just call in a domain expert anyway if it’s something that important. The other 99.9% - do they show up on time and work hard, do they care about the company, do they fit in with the rest of the team, etc, mostly can’t be determined in a short interview anyway.
And in particular, this was rampant at Microsoft in the Ballmer days.
This is why successful organizations shadow interviews.
It goes both ways - one interview turned into an acronym gotcha session. I quickly figured out that was not a place I would want to work; another friend that ended up working their later confirmed my suspicions.
Not really. The question was "Should you accept to play this game?" That is not a question where a number is an expected answer.
I’m assuming the context of making the guess is explaining the thought process. Otherwise how would that even come up?
I didn’t mean he passes the entire interview, just that he saw through the question and it’s probably best to move on to something else.
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.
"Is the computer operating on American electricity, or European?"
African or European. Everyone knows that.
How do you know so much about electricity?
I assume they keep a few jars of electricity at home.
Bunch of jars of electricity, just Leyden about the place? How much were you charged for them?
African and European electricity could be operating it together...
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.
They like to pretend their asking high level system design questions while actually quizzing candidates on esoteric low-level details.
And then if Ballmer assumes the other party assumes he's being adversarial we get into game theory.
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.
Seems like the distribution definitely won’t be flat since the guesser can randomly choose any of the numbers from 37 to 64 as a first guess without losing anything on the large side, so Ballmer starting with any of those increases his chance of having to pay out the $5. Likewise for other numbers there are nuances to what can be guessed.
But if you assume that the opponent knows that they shouldn't pick between 37-64, doesn't that change your odds?
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.
Yep, definitely not just what I said. I was saying that guaranteed it won't work out to an even distribution, not what the distribution would be.
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.
Any number between 36 and 64 should be as good!
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 :).
And then everyone gets nukes, or at least anti-matter mined in some vacuum chamber copperstatue configuration.
Never go in against a Sicilian when death is on the line!
Yes, this is a Nash equilibrium question.
So the actual problem here is to find Nash equilibrium.
I’d pay $5 to watch a short film of Ballmer asking this question to Wallace Shawn’s Vizzini.
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.
Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers.
You can also view it as a recurrence:
But your binary search tree example is more intuitive.Yes, you are right. In this game, you can know the answer after 6 guesses, but then you also have to tell him, which counts as the 7th guess.
You are correct that you can know the answer in 6, but actually winning requires you to “guess” that one last time once you know it.
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.
Although upon further thinking, you could then sprinkle in some binomial searches to abuse the uniformity. So the -0.64$ is merely a lower bound.
You forget that the quick guesses bring you more than $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.
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.
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.
Ballmer opens with "I'm thinking of a number between 1 and 100". If he uses your strategy instead that's a different scenario.
That’s only if you’re willing to trust Ballmer to do what he claims, which I wouldn’t.
Do you trust Ballmer to give you $1 in the cases where he's said he's going to give you $1? If not the EV calculation looks pretty bad...
they’re being adversarial within the framed rules of the game, not breaking the rules of the game?
Without writing the number down, it's up to Ballmer to decide that aspect, because you cannot look into his brain, or prove that he didn't commit to a prior number. Therefore, it's fair game.
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.
You should assume that your opponent is adversarial to your specific strategy.
Your calculation assumes that probability of each number is the same which is not true for adversarial choice.
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.
right but as posed the EV is positive if ballmer picks randomly so you have to go into consideration of the adversarial case
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.
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.
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 can actually do well combining different flavors of binary search! I commented a solution on the parent post if you're curious.
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.
Speaking of adversarial choices, the interviewee may wish to clarify that this number is an int and not a float :-p
Yes, you can counter the adversarial choices and win at least 7 cents per game :)
https://gukov.dev/puzzles/math/2024/09/05/steve-ballmer-was-...
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?
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).