One of the things that we ask some of our interviewees is to give us a project that would answer the following:
We need a reusable library to manage phone books for users. User interface is not required, but we do need an API to create, delete and edit phone book entries. An entry contains a Name (first and last), type (Work, Cellphone or Home) and number. Multiple entries under the same name are allowed. The persistence format of the phone book library is a file, and text based format such as XML or Json has been ruled out.
In addition to creating / editing / deleting, the library also need to support iterating over the list in alphabetical order or by the first or last name of each entry.
The fun part with this question is that it is testing so many things at the same time, it gives me a lot of details about the kind of candidate that I have in front of me. From their actual ability to solve a non trivial problem, the way they design and organize code, the way they can understand and implement a set of requirements, etc.
The actual problem is something that I remember doing as an exercise during high school (in Pascal, IIRC).