I give them a problem to solve. I ask for an algorithm, not specific language. Something like: "A trip has a starting city and an ending city. There is a list of all the trips made by John. Where did he start and where did he finish?". Then the interview proceeds based on the answers I get. Most people do linear search. "How does this answer scale as the number of trip increases?" "What happens if he started and ended in the same city?" "What if the trips did not form one chain?" "Can you find how many chains there are?" "How will you speed up your code?".
More than the solution or the answer, I am looking to see if the candidate understands me and can he/she tell me what she/he is doing. If I say, "ok, Let us say you build a map between starting point and the trip index. Would that help you speed up your code?" can the candidate understand what I am saying, if he/she can't understand ask intelligent questions to understand me, do they show an interest in understanding and solving the problem, are they comfortable in communication etc.
Puzzles have their place. If you solve puzzle instantly, it just means you have seen it before. That gives me no input. If you muddle through the solution, it means it is a fresh puzzle. Opens up lots of avenues for communication, letting me ask questions, offer suggestions and hints, and see how these hints are understood etc. I take extreme pains to put the candidates at ease. Tell them up front, "I am not looking for a final finished correct answer. I am looking to see how you find the answer. So feel free to think aloud, tell me how you plan to solve the problem, ask me if something would work or not etc. "