I have found that for technical interviews, the following pattern works very well (hiring side):
0. Explain to the candidate this algorithm and why. It isn't magic, there are no right or wrong answers, just testing "fit". This is a case where foreknowledge does not change the outcome!
1. Get a basic grasp of technologies both interviewer and candidate have in common, via say, just chatting. This is vital -- find an area where you are both somewhat competent.
2. State a problem you don't know the answer to, something you are currently working out for your own projects, in terms of the mutual tech. VERY IMPORTANT: you must not have the best solution in mind when you bring up the topic.
3. Brainstorm on it together.
This provides more feedback in a valuable way than the classic brainteaser. You find out how the person thinks and problem solves -- you know, that thing you are hiring her to do. You find out how you and her work together. Even if no solution is reached, it is OK because there was no solution going it -- just a problem to be worked.
Your job in the interview is then to make sure you steer the discussion towards various tech and deep problems, coding issues, etc. Afterwards you will have a pretty strong idea of how it is to work with the candidate, which is quite useful for deciding if you want to continue to work with the candidate as an employee. Further if you've done well at the steering of the discussion, you have learned about candidate's technical depth, without setting up test/interview anxiety situations.