Comment by AdamTReineke | Hacker News Reader

Comment by AdamTReineke | Hacker News Reader

Parent Full thread

My all-time favorite interview was one when I was interviewing for an SDET intern position at Microsoft. That interview (one in a day of four interviews) featured a great progression: logic puzzle, code the fixed input solution, code the n input solution, test your solution.

The puzzle was (apologies to the interviewer, but it IS a common puzzle) the eight ball and balance problem, where one ball is heavier than the other seven and you need to use a balance scale to find the lightest of the balls in the minimum number of weighs. I'd heard of the puzzle but never worked it out. I initially jumped to the 3 weigh solution, but the interviewer challenged me to keep looking, so I kept thinking and I found the 2 weigh solution. He then asked me to write code that could solve the 8 ball problem. Pretty straightforward. Once I finished that, he had me adopt it to be able to handle [edit: any number of] balls. This tested my ability to abstract my code. Finally, he asked how I would go about testing the program and we talked through that.

I cannot wait to steal that progression when I end up doing technical interviews someday.

Anyone who's studied information theory would destroy that puzzle though. In the same way that someone with a physics degree would perform way above average on a "count the stars" question. Or someone whose dissertation was on computational biology would excel at a string-matching algorithm question.

It is an example of the interviewer (or company/process) mistaking a specific problem as representative of all problems. Presumably they're looking for someone with "general problem solving skills", rather than "knowledge of astrophysics".

You can interpret the response more broadly, though. In this case, it was probably pretty apparent that the person hadn't worked through the problem before, so it is indicative of problem-solving and attitude. If he'd recited the answer from memory that usually comes across and then you have to pick something from a different area. If, as an interviewer, you literally can't find a problem that the interviewee hasn't already thought about, (i.e., he or she knows about computational biology, astrophysics, information theory, etc and none of this was obvious from their resume and previous positions) that can also be a good sign.

It's easy to game your answer as an interviewee though. HN actually had a post a while back about someone who "interviewed" for a living while on unemployment; by the time he was done, he had mastered pretending to think deeply about the answer to any interviewing question.

It's possible, but I doubt it's easy. I assume that the "mastery" of thinking deeply about answering interview questions was self-reported, right? I'd be curious to know how many of the interviewers would agree with him about it.

This is something that's pretty easy to test out in practice interviews with friends. My experience is that it's a lot easier to come up with questions that require thought and insight to answer than it is to answer them.

> Anyone who's studied information theory would destroy that puzzle though. In the same way that someone with a physics degree would perform way above average on a "count the stars" question. Or someone whose dissertation was on computational biology would excel at a string-matching algorithm question.

And...all of this is information the interview panel typically has available when evaluating candidates, as well as the result of any exercises done as part of the interview.

> It is an example of the interviewer (or company/process) mistaking a specific problem as representative of all problems. Presumably they're looking for someone with "general problem solving skills", rather than "knowledge of astrophysics".

If the process uses just one and not a set of exercises spread across problem domains, and gives it a fixed weight in the evaluation process and considers it independently of the candidates resume, the rest of the interview, etc., treating each component orthogonally rather than evaluating them together holistically, that might be true.

But that's not a problem with the puzzle as a tool, that's a problem with how the tool is used.

Anyone who's studied information theory would destroy that puzzle though.

I understand this comment in a general sense--the scale's behavior represents two possible states, so you can use it to filter the answer space in O(log_2 N) ala binary search, and you can get away with O[(log_2 N) - 1] if you partition the answer space the right way.

But what's the information theoretic interpretation of the problem?

It is a source coding problem. Kind of like a Huffman code. Depending on how theoretical or applied your information theory coursework was, you might have worked out simple codes like these in class, and that might be an advantage.

It's actually very similar to your tree reasoning above. The information theoretic outlook uses the probabilities of each of the N states to make a more efficient code, but since there are no probabilities in this case, the two approaches pretty much coincide.

Incidentally, there are three possibilities with each weighing -- scale tips right, scale tips left, scale stays balanced. So your logs should be base 3. In coding language, you are transmitting ternary valued symbols.

And, you should dispense with the O() notation, because the lead constant matters very much in this puzzle, and it happens to be 1.

Thanks! Haven't taken a formal information theory class yet, but I'd like to soon.

If you are mathematically inclined and good with probability, it could be a lot of fun.

Everyone from McKinsey to Accenture makes the same mistake.

I got to say, interview puzzles, while hated by the jobless, are lots of fun to think about. That sounds like a fun interview.

Reply on news.ycombinator.com