BTW, I got one of my best interview questions from a problem I encountered there.
Undergraduates solve it in two minutes; people with a BS need 5; MS 20; PhD never, or as fast as an undergraduate. The iterative solution is much simpler than a recursive one, so the question identifies how well-tuned your instincts are to problem spaces. If you go straight for recursion, you'll be there all day.
I found that everybody who found the minimal solution used the same hand gesture while describing it.