Steve Ballmer's incorrect binary search interview question • Hacker News Board

Re: Steve Ballmer's incorrect binary search interview question

#251

Post by gukoff » Thu, Sep 05, 2024, 11:18 PM UTC

wrvn wrote: post #115

wrvn wrote: post #112

Earlier quoted context omitted.

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.

You forget that the quick guesses bring you more than $1!

As the original article says, on average you can win $0.20. But that's indeed the upper bound if we speak of the adversarial number picking.

Re: Steve Ballmer's incorrect binary search interview question

#252

Post by gukoff » Thu, Sep 05, 2024, 11:21 PM UTC

OneLessThing wrote: post #209

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…

Okay I did the simulation. I don't think this strategy actually works, but I initially thought it might like you did. One such nash equillibrium my sim found was having the Ballmer player mix between picking either end of the range (not always 1 or 100 but around those numbers). I have the Ballmer player winning with around $.85-$1.00 EV per round. The resulting player strategy was to also try to start their binary s…

You can actually do well combining different flavors of binary search! I commented a solution on the parent post if you're curious.

Re: Steve Ballmer's incorrect binary search interview question

#253

Post by penguin_booze » Fri, Sep 06, 2024, 6:05 AM UTC

throwaway_1more wrote: post #124

I recently interviewed for a senior level role for a complex domain (payments), this is an area I have more than a decade of experience. The interviews went flawlessly because I know payments inside out, not just in US but in UK and most EU jurisdictions. The funny bit is that the role being senior, influencing, soft communication skills and managing conflict are even more important than the subject matter expertise…

> He used this as justification to make a negative reommendation, claiming I don't have real-time payments experience.

There: the same situation, pre-enacted by Steve Martin in Pink Panther: https://www.youtube.com/watch?v=mBwn7ycR7_Y. Probing one's ancestry until the answer is 'farmers'.

Re: Steve Ballmer's incorrect binary search interview question

#254

Post by NeoTar » Fri, Sep 06, 2024, 10:04 AM UTC

extr wrote: post #146

mgkimsal wrote: post #113

Earlier quoted context omitted.

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…

Yes, I have used questions like this before for junior roles and the notes for the interview were something like: - Asked/did not ask clarifying questions - Did/did not (or could not, on prompting) verbally walk through their reasoning - Could/could not articulate which assumptions they felt were most important/why Nothing about the actual content of the question itself, or if your answer was approximately correct (I…

> Like assuming the population of the USA was 1 Billion people.

Is that comically bad? It's only like three times too much (if you're using the American, 10^9 billion), but we'd accept a much greater margin of error in some other assumptions (like in the classic 'how many Piano tuners are in the city', I think an assumption of 1-in-30 or 1-in-300 households having a piano (that would need tuning) all sound like they could be true!)

Re: Steve Ballmer's incorrect binary search interview question

#255

Post by [deleted] » Fri, Sep 06, 2024, 10:34 AM UTC

extr wrote: post #146

mgkimsal wrote: post #113

Earlier quoted context omitted.

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…

Yes, I have used questions like this before for junior roles and the notes for the interview were something like: - Asked/did not ask clarifying questions - Did/did not (or could not, on prompting) verbally walk through their reasoning - Could/could not articulate which assumptions they felt were most important/why Nothing about the actual content of the question itself, or if your answer was approximately correct (I…

[deleted]

Re: Steve Ballmer's incorrect binary search interview question

#256

Post by extr » Fri, Sep 06, 2024, 8:17 PM UTC

NeoTar wrote: post #254

extr wrote: post #146

Earlier quoted context omitted.

Yes, I have used questions like this before for junior roles and the notes for the interview were something like: - Asked/did not ask clarifying questions - Did/did not (or could not, on prompting) verbally walk through their reasoning - Could/could not articulate which assumptions they felt were most important/why Nothing about the actual content of the question itself, or if your answer was approximately correct (I…

> Like assuming the population of the USA was 1 Billion people. Is that comically bad? It's only like three times too much (if you're using the American, 10^9 billion), but we'd accept a much greater margin of error in some other assumptions (like in the classic 'how many Piano tuners are in the city', I think an assumption of 1-in-30 or 1-in-300 households having a piano (that would need tuning) all sound like they…

Totally my personal opinion, but not knowing the approximate population of the country you live in betrays a pretty serious lack of curiosity about the world. Obviously a judgement call on how far off is "far off", but it just gives a funny feeling, you know?

Re: Steve Ballmer's incorrect binary search interview question

#257

Post by NeoTar » Sun, Sep 08, 2024, 11:47 AM UTC

extr wrote: post #256

NeoTar wrote: post #254

Earlier quoted context omitted.

> Like assuming the population of the USA was 1 Billion people. Is that comically bad? It's only like three times too much (if you're using the American, 10^9 billion), but we'd accept a much greater margin of error in some other assumptions (like in the classic 'how many Piano tuners are in the city', I think an assumption of 1-in-30 or 1-in-300 households having a piano (that would need tuning) all sound like they…

Totally my personal opinion, but not knowing the approximate population of the country you live in betrays a pretty serious lack of curiosity about the world. Obviously a judgement call on how far off is "far off", but it just gives a funny feeling, you know?

True, but in the context of making a ‘finger in the air’ calculation, 1 billion or 100 million (approximating to the nearest power of ten) should be “good enough’.

And if you’re interviewing, consider that for a decent proportion of people it may not be the country they live in (at least at the time you’re asking the question).