As an interviewee my first question would be – are you going to play fair, and how can I verify it?
I guess you could just ask him to write the number down on a piece of paper, and reveal you the number at the end of the interview :)
Steve Ballmer's incorrect binary search interview question
51–60 of 257 posts
Re: Steve Ballmer's incorrect binary search interview question
#52Earlier 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."
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.
Re: Steve Ballmer's incorrect binary search interview question
#53As 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…
wat
Re: Steve Ballmer's incorrect binary search interview question
#54It is also unclear if one has to keep playing. The expected value is very different if after the fifth guess one can thank Balmer for the opportunity and walk away.
Re: Steve Ballmer's incorrect binary search interview question
#55Earlier 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…
[deleted]
Re: Steve Ballmer's incorrect binary search interview question
#56As an interviewee my first question would be – are you going to play fair, and how can I verify it?
I guess you could just ask him to write the number down on a piece of paper, and reveal you the number at the end of the interview :)
The candidate who can ask that is already better than the candidate that jumps straight into a solution. If I'm the interviewer, I'd be impressed with such a candidate.
And frankly this is a needed skill. Candidates who automatically think about adversarial scenarios tend to write more defensive code, not to mention fewer vulnerabilities.
Re: Steve Ballmer's incorrect binary search interview question
#57It is also unclear if one has to keep playing. The expected value is very different if after the fifth guess one can thank Balmer for the opportunity and walk away.
Good one!
Reminds me of the viral video, goes something like "I'll pay you $20 if I can pour 2 cups of water on your head" and then only pour 1 cup and walk away.
Re: Steve Ballmer's incorrect binary search interview question
#58Earlier 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.
Like this one: https://rachelbythebay.com/w/2011/07/27/ohreally/
Yes, that happens, and elsewhere she goes on about culture in tech.
Re: Steve Ballmer's incorrect binary search interview question
#59Is 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?
Re: Steve Ballmer's incorrect binary search interview question
#60The 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
Your calculation assumes that probability of each number is the same which is not true for adversarial choice.