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

71–80 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#71

Post by andrewflnr »

aeonik wrote: post #47
__coaxialcabal wrote: post #36

Earlier quoted context omitted.

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.

That's a (potentially) good perspective, but not how people use "technical" in the wild.

Re: Steve Ballmer's incorrect binary search interview question

#72

Post by hamburglar »

hulium wrote: post #49
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…

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

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.

Re: Steve Ballmer's incorrect binary search interview question

#73

Post by wisemang »

HarryHirsch wrote: post #58
ozim wrote: post #52

Earlier quoted context omitted.

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.

Like this one: https://rachelbythebay.com/w/2011/07/27/ohreally/ Yes, that happens, and elsewhere she goes on about culture in tech.

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.

Re: Steve Ballmer's incorrect binary search interview question

#74

Post by tasty_freeze »

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

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.

Re: Steve Ballmer's incorrect binary search interview question

#75

Post by dagw »

corecirculator wrote: post #43
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

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.

Re: Steve Ballmer's incorrect binary search interview question

#76

Post by NickC25 »

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.

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.

Re: Steve Ballmer's incorrect binary search interview question

#77

Post by HarryHirsch »

wisemang wrote: post #73
HarryHirsch wrote: post #58

Earlier quoted context omitted.

Like this one: https://rachelbythebay.com/w/2011/07/27/ohreally/ Yes, that happens, and elsewhere she goes on about culture in tech.

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.

Re: Steve Ballmer's incorrect binary search interview question

#78

Post by sobellian »

alexey-salmin wrote: post #64

Disappointing to see the Nash equilibrium missing from the analysis.

For reasons given in the comments, both players probably choose a mixed strategy at equilibrium. If someone actually managed to find / prove a mixed strategy equilibrium for this game right there in the interview you probably couldn't go wrong hiring them on the spot.

Re: Steve Ballmer's incorrect binary search interview question

#79

Post by EricE »

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.

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.

Re: Steve Ballmer's incorrect binary search interview question

#80

Post by moritonal »

NickC25 wrote: post #76
ozim wrote: post #52

Earlier quoted context omitted.

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

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