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.
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".
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.
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.
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'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.
On the one hand, it gets at some important java concepts: hashCode() and equals() and the relationship between them. Depending on how they go about it, you can also get into issues of runtime complexity, memory/speed tradeoffs, etc... It's a deep question that offers a lot of room for exploration.
On the other hand, as mentioned, people usually do fairly poorly at it, and so my fear is that it's simply too difficult. I mean, I'd even be satisfied with solutions storing key/value pairs in a list -- inefficient, but workable -- but it's fairly rare that folks even get that close.
I've been perfectly happy with people who didn't get the "right" answer to some question.
The guy said "You want me to tell you?" I said "yeah."
I've been here a year.
As a candidate I'm not particularly good at solving puzzles in this kind of situation, but I'm not bothered when people present them because the discussion and interaction about the puzzle matters more to me than getting the answer.
As an interviewer it is important to ask questions that a candidate cannot answer to see how they react. Since I'm a slow thinker myself, I must sometimes resort to "unfair" questions. I don't expect an answer, I expect a reaction.
After establishing a friendly rapport, finding common technical background, presenting an "unfair" puzzle, and discussing the puzzle a bit, then a discussion like this is golden:
Candidate: "Do you believe my ability to solve this puzzle indicates how well I could do this job?" Me: "No. Though I often enjoy puzzles, I'm not particularly quick with them myself." Candidate: "Then why ask a question like this?" Me: "Because I want to see how you react when you don't know an answer right away. In your case, I had to resort to tricks."
In the context of an interview, that would just make me horribly frustrated--because my default response to not knowing the answer to a question, nor even being able to perceive a method to resolving my ignorance, is to go out and research the problem.
Whether on the Internet, or by asking my coworkers, or finding an expert, or just running actual experiments and seeing a pattern in the large pile of data generated, this is usually "the" way to get a problem solved, and what I spend nearly 80% of each working day doing.
I don't rely on "sudden gusts of inspiration blowing through me" to solve problems, because the time that could take to happen is unbounded, and it can't be made to scale, unlike research, which can be delegated as you please.
But obviously, research is a tool entirely taken away from you in an interview. The only thing you can do to find out more about the problem is to ask the interviewer themselves--at which point you're basically playing a game of 20 questions, where instead of getting all the data you'd realistically expect in response to each query, you get dealt out precise quantities of informational entropy to string you along.
This contrived situation is not one that applies to the average day in the workplace, and being made annoyed by it is no useful measure of how one reacts to real non-obvious problems.
The best candidates will recognize and comment on the ways in which frustration can be either constructive or destructive.
"This contrived situation is not one that applies to the average day in the workplace," is a serious over-generalization. Enormous amounts of code are written based on contrived beliefs about the way business does or should operate. The world would be much better off if programmers were better at recognizing and constructively commenting on these artificialities.
You can still see them in some places I believe. I've heard anecdotally that Microsoft is still a fan of them.
I should add that my personal experience contrasts with yours - I did a lot of interviews around 2004 and got asked riddle-type questions by one, maybe two, people. My memory is that they mostly died with the original dot-com boom.
That said, the fact that it was first introduced by a highly successful company doesn't lend it any merit in my book.
[1] http://blogs.msdn.com/b/bgroth/archive/2004/09/27/235071.asp...
www.youtube.com/watch?v=ALiqAXiTQBg
It's important to make this distinction because skills like deduction are actually critical to developers, i.e. identifying the source of buggy behaviour.
Maybe I'm not a star :)
I can sort of see how implementing my own hash table fits into a dev job, but I why manhole covers are round, or light bulbs in a room has absolutely nothing to do with anything relevant in our field.
People who use logic puzzles as proxies for anything in an interview have my everlasting scorn.