Even then, it's not the coded solution that I'm particularly interested in - it's the explanation that follows about how you got to that solution and the discussion about the pros and cons of your particular implementation. I'm looking for signs that you can solve problems and that you can look at your solutions with a critical eye and understand their weaknesses as well.
For what it's worth, the nastiest interview question I've ever had involved building and searching interval trees with up to a billion intervals stored in it where they were looking for solutions which provided the fastest posible search times. It was less than fun.
