I have over the last 8 years or so become terrified of interviewing techniques that revolve around having a conversation with a candidate, even (or, in fact especially) directed conversations.
Like many others before me, I've discovered that there is a huge gap between the ability to talk intelligently and productively about solving programming problems, and being able to actually solve programming problems. It's fine to hire someone who can reason through and discuss solutions... as long as you're also going to hire someone who will write the code for them.
Otherwise: get sample code, and watch them code something.