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

231–240 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#231

Post by meindnoch »

a57721 wrote: post #205
readyplayernull wrote: post #163

Slowly and for the span of many years I've come to realize that binary search is an amazing problem solving tool, specially on systems that are too big and complex to debug. For example, recently a colleague had a problem with a rendering tool for Figma, of which we don't have the source code. The tool would take too long exporting a specific design. The team mate tried changing things randomly for days to no avail.…

I recall a story about a private mailing list with ~1000 participants, where someone was leaking all the messages to the public. To quickly catch the responsible subscriber, the admin used binary search and selectively altered the messages by inserting an extra blank character somewhere.

This is where binary search is not necessary. The admin could have just sent out unique messages, by making binary variations at 10 locations in the email (or ternary variations at 7 locations, or quaternary variations at 5 locations, etc.). E.g. choose 10 words, that can be replaced with a synonym, then generate 2^10 = 1024 unique messages to identify the leaker.

Re: Steve Ballmer's incorrect binary search interview question

#232

Post by Closi »

notfed wrote: post #145
eterevsky wrote: post #93

This is a game with imperfect information, and the optimal strategy for each player is probably different from "pick any number at random" and "run off-the shelf binary search".

How is it imperfect information? Isn't each guess made openly?

It's imperfect information because both players don't know the same information.

Perfect information = Chess Imperfect information = Poker

This fits into the latter category - if player 2 knew everything that player 1 knows, they would behave differently.

Re: Steve Ballmer's incorrect binary search interview question

#233

Post by gowld »

ckemere wrote: post #156

I really am curious about the Nash equilibrium solution. I assume that as a commenter has mentioned, for the guesser it involves returning random numbers near the binary search. But I’m curious if for the picker it involves a uniform or non uniform initial distribution?? I’m sure someone on HN knows/can explain?

I don't see how Ballmer randomly guessing a number and candidate doing binary search would NOT be Nash Equilibrium.

For anything else, the candidate has a strategy of "guessing a trick number", and Ballmer has a strategy of "not choosing a trick number".

The candidate can't force Ballmer to try to be tricky.

Re: Steve Ballmer's incorrect binary search interview question

#235

Post by gowld »

netmare wrote: post #127
tantalor wrote: post #57

Earlier quoted context omitted.

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.

IANAL, but they either have to honor the verbal contract (pour an additional cup AND pay $20) OR the contract is void and therefore they can be sued for assault. Of course, the "can" in "if I can" may be construed as "being able to", but that's up to the jury I guess.

Pouring more water isn't required, only the permission to pour more water is required. And that was granted in this scenario.

As the old saying can go, "It depends on what the meaning of 'can' can be."

Re: Steve Ballmer's incorrect binary search interview question

#236

Post by quuxplusone »

ckemere wrote: post #156

I really am curious about the Nash equilibrium solution. I assume that as a commenter has mentioned, for the guesser it involves returning random numbers near the binary search. But I’m curious if for the picker it involves a uniform or non uniform initial distribution?? I’m sure someone on HN knows/can explain?

I've taken a stab at analyzing the game for 3, 4, and 5 numbers here: https://quuxplusone.github.io/blog/2024/09/04/the-game-is-fl...

There's obviously a huge gap between the 5-number game and the 100-number game; it's possible that the best mixed strategies settle down as the number of choices gets larger, or (for all I know) it's possible that the best mixed strategies get crazier and crazier. I'd love a ping if anyone does any real exploration of the 6-, 7-, etc.-number games.

Re: Steve Ballmer's incorrect binary search interview question

#237

Post by HarryHirsch »

rpdillon wrote: post #121
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 strongly agree with the sibling comment that this is a perfectly valid interview question. One of the biggest red flags in an interview is if I ask a question and the person doesn't know how to say 'I don't know', because it suggests there's a big risk that if I assign them a task in their day-to-day work, they won't tell me if they feel unprepared to tackle it. That's a far bigger issue than not knowing that trace…

The problem with "I don't know" is that it's really not culturally appropiate to say! Americans are supposed to be rugged, resourceful individualists and asking for help is frowned on because it shows weakness. Can't do that in an interview!

Re: Steve Ballmer's incorrect binary search interview question

#239

Post by LudwigNagasena »

twelve40 wrote: post #222
LudwigNagasena wrote: post #157

Earlier quoted context omitted.

He was being polite and understanding. They aren’t in a job interview setting, it’s not a correct frame to judge. But if it were, she would totally fail with that attitude of not thinking through the problem. That’s what his comment about stepping back meant.

Well even if they were in an interview setting, how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work? They made so much money in the 90's that they could smash every other Ivy league candidate with a bat or make them do 500 jumping jacks…

> how often in your day-to-day are you put on blast, being critically watched and scrutinized while having to give birth to an elegant solution to some stupid random question? How often does this solve-immediately-or-GTFO happens at work?

Well, honestly, once to several times a week during backlog grooming, meetings with stakeholders and other similar stuff. I find it much easier to work with people with fast recall who can be confident and correct even under time pressure. Nobody wants to sit through many time-consuming meetings that end with “we will check that and get back to you later”.

There is a succinct chess joke that summarises what being an expert means: a journalist asked Casablanca how many moves he thinks ahead. He replied, only one, but it is always the best one.

Re: Steve Ballmer's incorrect binary search interview question

#240

Post by inputError »

cbsmith wrote: post #118
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.

This is why successful organizations shadow interviews.

[dead]
Post reply on HN