Real-world problem solving is often very different than the very clean-cut computer-science exercises that companies tend to throw at candidates, which nominally have a set of solutions, only one of which is "correct" (in terms of computational complexity).

Personally, I'm a big fan of one of two styles of interviewing.

Pair interviews are great, because they are the closest thing to a real-world test-drive that you can get. During a pair interview, you work on real production code, with a member of the team that you will be working with, and at the end, it's pretty easy to tell whether or not the Thunderbirds are "go".

For non-pairing teams, I usually go with a simple (think "fizzbuzz") programming exercise, followed by a combination of collaborative problem-solving sessions with members of the team, exploring the candidate's background (what problems have they solved in the past?), and also a check to make sure that there's a fit in terms of engineering culture (somebody that hates TDD will hate working with me, for instance).