Then I came up with an alternative solution.
Step 1: Kill 9 mice.
Step 2: Have the mouse drink from a wine bottle.
Step 3: Wait to see if he dies. If he dies you found the right bottle. If he doesn't take the next bottle and go to step 2.
It's a fun question, but the best response I've heard to this is, "Move. You're never going to get laid with rats at your place during a party."
I think it comes down to most people (myself included) having a hard time recognizing competency and skill outside their own experience.
And then hope none of your guests call the SPCA.
Granted, your solution is better, but you can solve this problem without binary tricks.
This is a great puzzle but IMHO a terrible interview question, even if you're looking for C programmers. Interviews are about talking. I might be able to solve this puzzle (though not necessarily under pressure) but I'm quite sure this isn't a puzzle I could talk my way through out loud. At best, I'd sit around for minutes muttering under my breath and staring at the walls and pacing, and then state something approximating the answer. A waste of good interviewing time.
Remove the time limit and the puzzle isn't so bad. There's a nice stupid answer (the "99 bottles of wine on the wall" algorithm) and a progressive series of potential improvements (the "10-bottles-of-wine-on-the-wall played in parallel ten times" algorithm; the "mix the first N/2 together, mix the second N/2 together, feed the first batch to a mouse, iterate" algorithm, and finally you kind of parallelize that and get the ultimate answer). But you shouldn't expect to get all the way through that discussion in an interview -- and, if you state the time limit up front, you just scare the wits out of the candidate.
Two poison applications to find the right answer, so it only takes ten minutes. Lock the door and tell the guests who arrive you will be there in a minute so you have a bit of breathing room in which to prepare your bottles.
These follow-up questions, and the fluency with which the candidate navigates them, are actually the point of the exercise. Well, that and to learn whether or not you're talking to someone who can't properly state any algorithm, and to help gauge your candidate's level of primadonnatude. [1]
[EDIT: Okay, I typed this up before people stated the version of the question with the 2-mouse-lifetime time limit. That version is, IMHO, an awesome puzzle but too damn hard for an interview question.]
---
[1] There is no one ideal level of primadonnatude. It depends on the business, the role, and the company culture. Steve Jobs is, arguably, the prima donna assoluta of computing, and that seems quite appropriate for his job. On the other hand, a good second grade teacher, the sort of person who enthusiastically spends every day for fifty years instructing students in the subtraction of single-digit numbers, probably has very little primadonnatude.
one deck of cards..
1 have 28 cards dealt out and ask victim to pick their card
2 Deal out 4 card stacks, cards face up staggered stacked so that victim sees every card. & cards in each stack
3 have victim tell which stack their card is in..
How many more deals before you get their card in the first card position in a stack?
Answer, counting the first deal its 3 or less..
I used this example in a RealNetworks interview, they really did not get it..