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

61–70 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#61

Post by sltkr »

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…

Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers.

You can also view it as a recurrence:

  f(1) = 1
  f(n) = 2*f(n - 1) + 1 = 2^n - 1
But your binary search tree example is more intuitive.

Re: Steve Ballmer's incorrect binary search interview question

#62

Post by tcgv »

justusthane wrote: post #59

Is there a name for the fallacy where you attribute your success in life to your own intelligence, and thus assume that you are smarter than everyone else, and that you therefor must be right about everything? Sort of an opposite impostor syndrome?

> an opposite impostor syndrome?

Dunning–Kruger effect

https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect

Re: Steve Ballmer's incorrect binary search interview question

#63

Post by silvestrov »

justusthane wrote: post #59

Is there a name for the fallacy where you attribute your success in life to your own intelligence, and thus assume that you are smarter than everyone else, and that you therefor must be right about everything? Sort of an opposite impostor syndrome?

[flagged]

Re: Steve Ballmer's incorrect binary search interview question

#65

Post by jkaptur »

Some other interesting points here: Ballmer works hard to de-emphasize and diplomatically move away from discussing this exact question once it becomes clear that Chang's not approaching it by thinking explicitly about binary search and expected value.

Which is not surprising, because she's a professional journalist! It's amazing that Ballmer (like so many technical interviewers) is so pleased with this question that he couldn't help bringing it up, even though it's not really that relevant to Chang's question.

Re: Steve Ballmer's incorrect binary search interview question

#66

Post by mupuff1234 »

dannyw wrote: post #32
paxys wrote: post #20

As an interviewee my first question would be – are you going to play fair, and how can I verify it?

“As a SWE, I seek to understand important context first, before jumping to build or code. First, I’d like to ask if you’ll guess randomly and fairly, or adversarially?” “Secondly, when significant money is involved, I make sure to verify any inputs. I’m considering the situation, not you personally, untrusted. How can I verify it, or do you want me to proceed assuming that’s verified?” Those are great questions, but…

"as you, my interviewer, are a capable SWE I assume you gave me all the context needed to solve the problem".

The interviewing game of asking clarification questions is silly and should stop. In the system design portion I can understand it, but not when asked a direct technical question.

It's perfectly fine to ask followup questions with added constraints or just directly say that the specification is fuzzy and needs to be clarified first, but having that dance around the basic specs in nonsense (as if you wouldn't know if you're dealing with a 10PB array or 1kb at work).

Re: Steve Ballmer's incorrect binary search interview question

#67

Post by hamburglar »

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.

And in particular, this was rampant at Microsoft in the Ballmer days.

Re: Steve Ballmer's incorrect binary search interview question

#68

Post by jarito »

justusthane wrote: post #59

Is there a name for the fallacy where you attribute your success in life to your own intelligence, and thus assume that you are smarter than everyone else, and that you therefor must be right about everything? Sort of an opposite impostor syndrome?

Narrative Bias: https://en.wikipedia.org/wiki/Narrative_bias is pretty close.

Re: Steve Ballmer's incorrect binary search interview question

#69

Post by hulium »

sltkr wrote: post #61
hulium wrote: post #49

Earlier quoted context omitted.

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

Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers. You can also view it as a recurrence: f(1) = 1 f(n) = 2*f(n - 1) + 1 = 2^n - 1 But your binary search tree example is more intuitive.

Yes, you are right. In this game, you can know the answer after 6 guesses, but then you also have to tell him, which counts as the 7th guess.

Re: Steve Ballmer's incorrect binary search interview question

#70

Post by Jupital »

dannyw wrote: post #32
paxys wrote: post #20

As an interviewee my first question would be – are you going to play fair, and how can I verify it?

“As a SWE, I seek to understand important context first, before jumping to build or code. First, I’d like to ask if you’ll guess randomly and fairly, or adversarially?” “Secondly, when significant money is involved, I make sure to verify any inputs. I’m considering the situation, not you personally, untrusted. How can I verify it, or do you want me to proceed assuming that’s verified?” Those are great questions, but…

[flagged]
Post reply on HN