Earlier quoted context omitted.
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 problem…
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'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.