The goal of the problem solving interview is more to see the candidates reasoning process and less the ability to recall the problem and reproduce a solution. I like interviews where the problems are more open ended and the interviewer is active in the process and it's more of a discussion towards a solution and THEN coding or at least some pseudocode.

I've had interviews where I'll be asked some canned algo/data structures problem (some version of knearest, or longest substring) and then the interviewer will tune out- these are mostly lame.