We use a whiteboard in our interviews for sketching UI, and sometimes drawing a database table. Generally candidates find this much easier than talking through their design, and we think that interview very closely represents what we do on a day to day basis.
If you're asking candidates to balance a binary search tree when no one in the history of your company has ever had to do that, you're asking the wrong questions.
We do a mock technical meeting with multiple members of our tech team and the candidate presenting options, talking through pros and cons, etc. Much of the interview is about assessing communication rather than technical skills.
The interview is basically a standard tech meeting that we hold regularly in the team to discuss designs of new projects.
In my opinion it is all about aligning your questions with the day to day task you expect from people. If the work is very algorithm heavy, by all means probe for that in the interview.
I base my interviews around one main question: assume the tech challenge you written beforehand is a prototype for a complete product/service. what are the steps necessary to get us there and beyond?
I do not care about the candidates tech preferences or the exact solution as long as the argument for it is coherent and not just based on heresay. Then I probe for a couple of things within their solution where I see potential weaknesses based on their argument, experience or code in relation what we look for. It is more about problem solving, decision making and communication than computer science.
Candidates are free to just talk trought it or use whiteboard/paper to draw it out. But if you choose the former you better not forgett what you said five minutes ago.
Obscure “I had to google it before asking you” problems are the problem not the whiteboard. I think whiteboards are good visual aides.
Sometimes I just ask people to draw a frog though.