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."
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.
I think it comes down to most people (myself included) having a hard time recognizing competency and skill outside their own experience.