O(2^n) is pretty horrific, though. ;)
In fact I usually try to shy away from coding a quiz that has 'a trick'. I usually want to see you do indeed have a decent grasp on the language, can properly decompose a problem, you can finish in front of me and quickly, and most importantly ask questions to clarify. I also try to stay away from things that require a particular framework. As those come and go and usually people can learn new ones fairly quickly with some good examples. I also ask if they have read any of the 'coding interviewing' books and what they thought. Usually if they can understand those books they are fine on complexity issues.