Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Steve Ballmer's incorrect binary search interview question

blog.jgc.org

Post reply on HN
Print view View original

41–50 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#41

Post by toolz »

cwmma wrote: post #33
toolz wrote: post #3

Title is wrong in implying Balmer is incorrect and the article shows that the title is wrong. If clickbait is misleading, then this is worse than clickbait, no? > Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you... The article goes on to show that there are numbers where a binary search always has the guesser paying $1

the article focuses on the next part of that sentence > secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer

and given that the first rule still holds where he chooses hard numbers, then the expected value of the game is negative (aside from meta-gaming this, which is out of scope for a technical problem)

Re: Steve Ballmer's incorrect binary search interview question

#42

Post by mrgoldenbrown »

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…

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

Re: Steve Ballmer's incorrect binary search interview question

#43

Post by corecirculator »

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…

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

Re: Steve Ballmer's incorrect binary search interview question

#44

Post by Eumenes »

__coaxialcabal wrote: post #36
Eumenes wrote: post #2

Didn't Steve Ballmer start off at MSFT essentially in a biz ops role, supporting execs when the company was super small? Interesting how he became technical as the company grew. Pretty rare.

It's surprising the extent to which the tech community overfits towards classifying intelligent individuals as either exclusively technical or nontechnical. Recruiters are especially weak in this regard, e.g., if you've ever been effective at sales or people leadership, you are likely ineffective at swe or data science or vice versa. The most intelligent folks I've worked with are very diverse in their interests and…

Because we live in an era of specialization. Look at a companies job page - even startups have silos. I don't think this is strange or unusual. Its hard to be good at everything. If I'm spending 8+ hours per day doing sales, where am I going to find the time to be good at other things? Most people are working for the weekend or to spend time with their families. Diving into far off subjects related to work isn't always exciting.

Re: Steve Ballmer's incorrect binary search interview question

#45

Post by cjfd »

jgrahamc wrote: post #14
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…

And then if Ballmer assumes the other party assumes he's being adversarial we get into game theory.

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.

Re: Steve Ballmer's incorrect binary search interview question

#46

Post by pxx »

michaelt wrote: post #16
toolz wrote: post #3

Title is wrong in implying Balmer is incorrect and the article shows that the title is wrong. If clickbait is misleading, then this is worse than clickbait, no? > Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you... The article goes on to show that there are numbers where a binary search always has the guesser paying $1

Also the number only exists in Ballmer's mind, so if he wanted to, he could change it to be unfavourable should you make a lucky guess. Here, you can play the game with me. Higher. Lower. Higher. Higher. Lower. Correct. Six guesses, you owe me $1.

your point is valid but you cannot have a static answer list.

if I started off by guessing 50 twice you're cooked. or 50 and 52.

Re: Steve Ballmer's incorrect binary search interview question

#47

Post by aeonik »

__coaxialcabal wrote: post #36
Eumenes wrote: post #2

Didn't Steve Ballmer start off at MSFT essentially in a biz ops role, supporting execs when the company was super small? Interesting how he became technical as the company grew. Pretty rare.

It's surprising the extent to which the tech community overfits towards classifying intelligent individuals as either exclusively technical or nontechnical. Recruiters are especially weak in this regard, e.g., if you've ever been effective at sales or people leadership, you are likely ineffective at swe or data science or vice versa. The most intelligent folks I've worked with are very diverse in their interests and…

Technical is just a code word for "having a detailed understanding of something".

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.

Re: Steve Ballmer's incorrect binary search interview question

#48

Post by enneff »

mrgoldenbrown wrote: post #42
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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#49

Post by hulium »

thedavibob wrote: post #38
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 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…

> Given that 7 guesses covers 128 numbers

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.

Re: Steve Ballmer's incorrect binary search interview question

#50

Post by zeroonetwothree »

I believe you’d have to do a game theory analysis to actually get the answer (compute the mixed strategy that produces a Nash equilibrium). My intuition is that this yields <0 EV (because it’s already so small against a uniformly random strategy, which can’t be optimal) but I didn’t do the calculation.
Post reply on HN