Read this first: Tests for Programming Interview: Part 1.
In Part 2 article I'll describe how I personally would write the code specified in Part 1. I'm not claiming this is in any sense objectively the best, and I'm certainly not suggesting it's the only.
The main point of the whole exercise is to see if the candidate can write any code - anything after that is a bonus. As it says in Part 1, what the candidate writes is the starting point for the discussion that follows.
And in case you haven't yet, and want to try it for yourself before you see my code, go visit Tests for Programming Interview: Part 1 before you click through to the article proper.
Otherwise, here's the discussion of how I'd write it: Tests for Programming Interview: Part 2