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

201–210 of 257 posts

Re: Steve Ballmer's incorrect binary search interview question

#201

Post by LudwigNagasena »

dagw wrote: post #75
corecirculator wrote: post #43

Earlier quoted context omitted.

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.

You should assume that your opponent is adversarial to your specific strategy.

Re: Steve Ballmer's incorrect binary search interview question

#202

Post by zerr »

AmericanChopper wrote: post #192
zerr wrote: post #187

Earlier quoted context omitted.

What you should care is a behavior. You should be open about what is expected. People change behavior all the time depending on the situation/group/company/context.

People can change the behaviour for brief periods. But who they are day in day out is going to be pretty consistent. Telling people how I would want a good candidate to behave during an interview doesn’t help at all with candidate selection. An inclination towards saying things they think people want to hear is a characteristic I’d like to select out of my candidates as well, so perhaps I’ve been killing two birds wi…

> People can change the behaviour for brief periods.

This is a false assumption. Especially generalizing the behavior in such an adversarial setup as a job interview to a regular day to day work/life.

> Telling people how I would want a good candidate to behave during an interview

You should tell them the rules of the game. The thing is, with interviews, there are already predefined assumptions, such as not knowing something takes a point from you, so people avoid this. In your case, you are altering these assumptions without disclosing it. So people might already had changed their behavior for the interview specifically - avoiding admitting not knowing something.

Re: Steve Ballmer's incorrect binary search interview question

#203

Post by indrora »

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

In the networking classes I took, we used binary search to determine where a problem was occurring, but with a slight twist: Each step away from the end device (e.g. workstation, etc.) take two steps upwards in the network. This broadened your scope easily but allowed for very fast refinement of "These are fine, but this is broken".

Re: Steve Ballmer's incorrect binary search interview question

#204

Post by extr »

crazygringo wrote: post #194
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…

Yeah, I think there's a possible pitfall with using this as an interview technique though. When you're in a real situation with a customer or user, you ask tons of questions. You use a lot of common sense to figure out what they really want, what's actually important, etc. But often times these interview questions -- like how many vacuum cleaners in a city -- don't need any further questions asked. The idea that you'…

Yeah I mean the vacuum landfill thing is stupid. The point was never to try to trip people up, there's no wrong answer (or question), just find out if they could recognize ambuiguity. "Let's try to estimate the amount of pet food sold each year in the USA." -> "Dogs and cats too?", "In terms of dollars or pounds of food?" type of stuff. This was for analyst roles - basically your whole job would be something similar to this where you're asked ambiguous questions and you need to translate that into a semi-rigorous analysis, infer intent, etc. I hate to say it but if you didn't realize that going into the interview, you were probably not a good fit as an analyst in the first place!

Re: Steve Ballmer's incorrect binary search interview question

#205

Post by a57721 »

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.

Re: Steve Ballmer's incorrect binary search interview question

#206

Post by roninorder »

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

In the old days of DHTML when I was in my early teens this was the way I debugged very messy JS scripts (like multi-level menus). Remove some code - see if it still breaks, remove more, and so on.

Re: Steve Ballmer's incorrect binary search interview question

#207

Post by Salgat »

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

In electricity we do the same. Measure continuity at the halfway point to see if the wire is broken on that half. Rinse and repeat.

Re: Steve Ballmer's incorrect binary search interview question

#208

Post by 93po »

talldrinkofwhat wrote: post #176
potamic wrote: post #135

Earlier quoted context omitted.

> they threw an obnoxious senior manager that kept interrupting me as I calmly answered the questions This is a red flag. To me this signals that a company not only has a toxic culture, but embraces it. Such places attract personalities who love conflict and once there are enough people, they set the culture. What doesn't get said often is that conflict is a failure of leadership. Often all it takes to resolve confli…

The way I read it:they inserted the manager as a litmus test AGAINST aggression / toxic culture. Kind of like when a psychology test is given, the __thing__ they're trying to measure is always one level removed / abstracted to avoid subjects gaming the system. I suppose deceptive practices in interviews don't bode well, but I could see the argument given the interviewee could be deceptive (something that this site co…

I think the point is that deliberately trying to piss someone off and annoy them is a super childish and ridiculous thing to do and is indicative of a place I wouldn't want to work. Interviewing is already stressful and terrible enough without deliberately being antagonized. Most people are not going to go off on someone doing this, they're just going to be turned off by the entire process and decline to go forward to the interview or hiring process.

I think a good comparison would be your romantic partner "testing" you by asking their friend to try to sleep with you and see if you try to go through with it. This is toxic, manipulative, sociopath level behavior.

Re: Steve Ballmer's incorrect binary search interview question

#209

Post by OneLessThing »

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 search at the extreme ends of the range and hope they guessed the right side. It's kind of like the soccer penalty kick dynamic between the shooter and goalie. Goalie wants to pick the same side, shooter wants opposite sides. But with 100 choices, the goal is too wide I think.

I now think that not constraining the players remaining choices to follow binary search pattern would completely change the resulting equilibrium and improve the results for the player. But that would be more computationally demanding to calculate because there's a strategy choice for every range of choices. And also I've avoided work for 2 hours by working on this so that's not great haha. I _am_ curious what not constraining the player to binary search would do though...

Re: Steve Ballmer's incorrect binary search interview question

#210

Post by eureka-belief »

The best interview that I ever had was one in which the dude wore a fedora and we white-boarded. And yes we talked about algorithms. But I got the sense that he didn’t care if I knew any particular thing per se so much as was trying to figure out if I would be a fun person to jam with on hard problems.

Deep down we all know what programming, was supposed to be about, which is when you drop the ego and channel your childlike creative curiosity to create something you love, or to find like truth. People who know how to reliably find this state and enjoy it will become an “intelligent” person regardless of their original IQ. When I hire a full time role now, I look for people who are best able to channel this in the context of our team and our mission.

The problems come in when the creative output of the programming is being managed in a capitalistic system. If you take capital with the plans to build something and make money, then you have an entirely new set of constraints. You committed to a deadline so now you lose the ability to say “no”. Most programmers hate scrum/agile with a passion because these processes are basically the manifestation between the conflicts and misunderstandings that happen between shareholders and creators.

Post reply on HN