When I was interviewed for my second programming job, I was asked to write a function that prints the nth Fibonacci number. I scratched it out on a piece of paper, and apparently that was so rare the interviewer suspected someone from the company had leaked the answer to me, knowing it was his stock question.
I used to ask the following question as my “hard” question. It showed up some years ago on the Boston Perl Mongers mailing list. People didn’t have to produce working code, but it was helpful to see their thought process:
You have the numbers 123456789, in that order. Between each number, you must insert either nothing, a plus sign, or a multiplication sign, so that the resulting expression equals 2001. Write a program that prints all solutions. (There are two.) This is a pretty tricky problem, actually, if you don’t think to use recursion. I was satisfied with pseudocode, but the Perl Mongers version was to fit the whole thing into 80 characters!