Steve Ballmer's incorrect binary search interview question • Hacker News Board

Re: Steve Ballmer's incorrect binary search interview question

#171

Post by baking » Tue, Sep 03, 2024, 7:22 PM UTC

gweinberg wrote: post #139

kibwen wrote: post #10

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 se…

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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#172

Post by chihuahua » Tue, Sep 03, 2024, 7:22 PM UTC

Another stupid gotcha:

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

Re: Steve Ballmer's incorrect binary search interview question

#173

Post by jefftk » Tue, Sep 03, 2024, 7:34 PM UTC

layer8 wrote: post #159

jefftk wrote: post #111

Earlier quoted context omitted.

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

Re: Steve Ballmer's incorrect binary search interview question

#174

Post by HarryHirsch » Tue, Sep 03, 2024, 7:39 PM UTC

SonOfLilit wrote: post #152

HarryHirsch wrote: post #104

Earlier quoted context omitted.

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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#175

Post by vladimirralev » Tue, Sep 03, 2024, 7:49 PM UTC

baking wrote: post #168

kibwen wrote: post #10

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 se…

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'…

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.

Re: Steve Ballmer's incorrect binary search interview question

#176

Post by talldrinkofwhat » Tue, Sep 03, 2024, 7:51 PM UTC

potamic wrote: post #135

throwaway_1more wrote: post #124

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…

> 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 confli…

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

Re: Steve Ballmer's incorrect binary search interview question

#177

Post by [deleted] » Tue, Sep 03, 2024, 8:03 PM UTC

kstrauser wrote: post #162

AmericanChopper wrote: post #128

Earlier quoted context omitted.

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 know…

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, pleas…

[deleted]

Re: Steve Ballmer's incorrect binary search interview question

#178

Post by authorfly » Tue, Sep 03, 2024, 8:08 PM UTC

readyplayernull wrote: post #163

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

It shocks me that people don't think to do this more quickly generally (even intuitively).

Re: Steve Ballmer's incorrect binary search interview question

#179

Post by more_corn » Tue, Sep 03, 2024, 8:08 PM UTC

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

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

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

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

Re: Steve Ballmer's incorrect binary search interview question

#180

Post by AmericanChopper » Tue, Sep 03, 2024, 8:09 PM UTC

zerr wrote: post #166

AmericanChopper wrote: post #128

Earlier quoted context omitted.

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 know…

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

Interviewing is by no means the perfect way to assess a candidate, but ultimately that’s what the purpose is. If I just tell candidates what I want them to say upfront, then why even bother with it at all? I want to assess what qualities they have that I want/don’t want, and what qualities they don’t have, as best I can. They don’t need to be perfect. Skills can be trained, personality characteristic much less so. People are flexible enough that some of them could spend one hour flexibly pretending to be the candidate I’m looking for, but that’s not the purpose of the exercise for me.