The question about mice seemed sort of neat to me at first. I figured the desired solution was splitting the wine into two groups, taking the group that turns out to be poisoned, and then recursing.
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.
He left out that there's a time limit. You have a party with guests coming over in 10 minutes, and it takes 5 minutes for the wine to kill the rat (in any dosage amount). Given those constraints, how do you do it?
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."
He's testing if you can think in binary. Label the bottles of wine with binary numbers, 0000001 to 1100100. Give the first mouse every other bottle of wine, the second mouse every bottle of wine with a 1 in the 2's place, the second mouse every bottle with a 1 in the 4's place, etc. If a mouse dies, the poison lies in one of the bottles it was given. If a mouse survives, there is no poison in any of the bottles it was given. Since every combination of mice is associated with a unique bottle, you can read off the digits formed by the dead and live mice to determine which bottle it was.
Given the constraints (10 minutes total, 5 minutes for poison to kill), you can also divide the wine into 10 groups and assign each group to each of the 10 mice. The mice then drink samples from every bottle in his group, and after 5 minutes, the one that dies has the group with poison in it. You then assign each of the rats a bottle from this group, and then see which one of them dies. If they all live, then the remaining bottle is poisoned.
Granted, your solution is better, but you can solve this problem without binary tricks.
Thanks for this additional information. Now I finally see what geuis is talking about.
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.
Split it into ten groups of ten with a mouse per group. One mouse dies. Split that mouse's group into ten groups of one with one mouse for each group. There is a leftover group since one of your mice died, but it doesn't matter. If none of the other mice die you can deduce that the untested bottle contains the poison.
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.
Yeah, the answer is actually bit math if I can remember. And I'm sure these kinds of questions are right for some kinds of positions, but they aren't appropriate for frontend engineers. It was fun to try and figure out though. If the question was "you have 10 mice, 10 bottles of wine, and a house full of people that you want to leave, what's the most efficient way?" then that's something that has merit. That involves thinking about compression methods and shoving people (data) through limited exits as quickly as possible. That's a relevant question.
Yup, it's bitmath. I happen to know which company's asking that variation of the question right now. Interesting to see good companies miss the mark in interviewing so widely.
I think it comes down to most people (myself included) having a hard time recognizing competency and skill outside their own experience.
A fine opening, because not only is it the stupidest algorithm that could possibly work, but it also tees up the obvious follow-up questions: "How efficient is your method? How much time will it take in the worst case? How much in the best case? How much in the average case? Can you improve on this?"
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.
The thing I loved about the second solution is that it actually performs better at scale. I love the irony of the function with the higher growth rate being the better function as the number of wine bottles increases.
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.