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

111–120 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#111

Post by jefftk »

layer8 wrote: post #100
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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#112

Post by wrvn »

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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#113

Post by mgkimsal »

crazygringo wrote: post #103
NickC25 wrote: post #76

Earlier quoted context omitted.

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

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

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.

Re: Steve Ballmer's incorrect binary search interview question

#114

Post by jareklupinski »

tasty_freeze wrote: post #74
mrgoldenbrown wrote: post #42

Earlier quoted context omitted.

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

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

"Is the computer operating on American electricity, or European?"

Re: Steve Ballmer's incorrect binary search interview question

#115

Post by wrvn »

wrvn wrote: post #112
thedavibob wrote: post #38

Earlier quoted context omitted.

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

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.

Re: Steve Ballmer's incorrect binary search interview question

#116

Post by furyofantares »

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…

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.

Re: Steve Ballmer's incorrect binary search interview question

#117

Post by cbsmith »

jareklupinski wrote: post #114
tasty_freeze wrote: post #74

Earlier quoted context omitted.

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

> 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? "Is the computer operating on American electricity, or European?"

African or European. Everyone knows that.

Re: Steve Ballmer's incorrect binary search interview question

#118

Post by cbsmith »

ozim wrote: post #52
enneff wrote: post #48

Earlier quoted context omitted.

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.

This is why successful organizations shadow interviews.

Re: Steve Ballmer's incorrect binary search interview question

#119

Post by enneff »

jncfhnb wrote: post #92
enneff wrote: post #48

Earlier quoted context omitted.

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.

> I see you passed this guy after a single guess. Why was that? > Well, he guessed 69, sir, so I assumed he was doing some serious game theoretic calculations

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.

Re: Steve Ballmer's incorrect binary search interview question

#120

Post by enneff »

krisoft wrote: post #94
enneff wrote: post #48

Earlier quoted context omitted.

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.

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?
Post reply on HN