Shane Bell does a write-up of an interview he went through. Apparently the company just dumped a programming exercise on him and left him with a pencil and paper for an hour. Nasty!

While the basic idea of a "real" programming test at interview is great, asking someone to do it with a pencil is just plain daft! This is a perfect example of cargo-culting. They know they should get people to program in an interview, they know they should ask a "tough" question. But then they invalidate the whole thing by testing "pencil-based-programming-acuity"! Whatcha building guys? A Babbage engine? Um, you know, how difficult is it, if you are going to the trouble of all this testing, to set up a locked down machine with no internet access?

Anyway, Shane runs through the exercise and his solution. He does pretty well. He also asks if there's a better solution.

Yes, Virginia, there is a Santa Claus!

And he lives at MIT OpenCourseWare. Specifically, the AI search lectures. Fantastic stuff.

Looking at the problem they gave Shane, finding a path through maze from top-right to bottom-left, it looks like you could throw an A* search at it and do pretty well. Add some iterative-deepening if you're feeling fancy and want to handle big mazes. Basically, you try to predict the best direction by calculating your current straight-line distance from the goal square at the bottom right, and choosing the next square as the one that gets you closest. If you get stuck in a cul-de-sac, backtrack out of it (Shane does use backtracking).

So how do you beat these nasty interviews? Know your search algorithms! Most of these "puzzles" can be solved with some sort of search. I'll bet you anything the guys who set this question where either a.) clueless, so a good algorithm will really impress them, or b.) not clueless and actually looking for a proper algorithm like A*. Either way you win!