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

11–20 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#11

Post by paxys »

kevincox wrote: post #9
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

But if you know the number picker is going to choose these numbers you can optimize your algorithm.

How do you know that?

Re: Steve Ballmer's incorrect binary search interview question

#12

Post by toolz »

kevincox wrote: post #9
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

But if you know the number picker is going to choose these numbers you can optimize your algorithm.

but you don't know. Only he knows that he's going to pick numbers the binary search will fail on and he states as much as his reason that you shouldn't play the game.

Re: Steve Ballmer's incorrect binary search interview question

#14

Post by jgrahamc »

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.

Re: Steve Ballmer's incorrect binary search interview question

#15

Post by ezero »

sudo_bang_bang wrote: post #7
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.

He graduated with a mathematics degree from Harvard so the concept of binary search would have likely been familiar to him. But you’re right, as far as I can tell, he never did any technical work like programming in his career.

Not only that, he was also better than Gates at math. From the acquired podcast episode on Microsoft:

> Ben: He's gregarious. Anyone who's ever met Steve or seen a video of Steve, you are well aware that this man has a presence. But the thing that people don't know about him is he is so unbelievably analytical. Steve is the guy that outscored Bill Gates on the Putnam exam.

source: https://www.acquired.fm/episodes/microsoft

Re: Steve Ballmer's incorrect binary search interview question

#16

Post by michaelt »

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.

Re: Steve Ballmer's incorrect binary search interview question

#17

Post by Closi »

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

Although Ballmer could still be incorrect, because a 'sufficiently logical' player would also presumably know that he could pick numbers that'll be the most difficult to find via binary-search, so by the same logic you could also meta-game it, and assume any number that can be found in 5 steps with a binary search is immediately out. This would narrow the search space to only 37 numbers, which can then easily be found within 5 guesses.

But he also knows that you know that he could pick numbers that will be the most difficult... So could then pick one of the numbers that actually are guessable within 5 guesses to trick you.

But then you also know that he knows that you know that he could pick difficult numbers too.

I'm not entirely sure if this invalidates Ballmer's advantage, but I would be interested to know what the 'perfect' strategy would be for this game considering the meta-game.

Post reply on HN