> they want to know that you have the basic mental dexterity to figure things like this out
If you have the "mental dexterity" to coming up with your own solution which is identical to Dijkstra's pathfinding algorithms in terms of complexity within an hour interview, you are a god among mortals.
And that's what they expect - a solution to a problem that is equal to the best minds of our field. I say this from experience: I was expected to do exactly that, and criticized when I came up with a O(n^3) instead of O(n^2).
Solving a maze isn't identical to Dijkstra's algorithm. And Dijkstra's algorithm was specifically chosen to be an easy problem with an understandable answer, to show off a new computer. It was never some grand unsolved problem. Yes, it's reasonable to expect somebody with a modern data structures education who mysteriously hadn't heard of it to be able to invent it. Or to reinvent it, having forgotten it, because it's your basic breadth first search with care taken not to get "lost in the woods."
If you have the "mental dexterity" to coming up with your own solution which is identical to Dijkstra's pathfinding algorithms in terms of complexity within an hour interview, you are a god among mortals.
And that's what they expect - a solution to a problem that is equal to the best minds of our field. I say this from experience: I was expected to do exactly that, and criticized when I came up with a O(n^3) instead of O(n^2).