I was contacted by a recruiter after posting and applying to multiple positions online. The recruiter set up a phone interview with one of the members of the iPhone Applications team.

The interview started on time. After introducing each other, the manager quickly began to ask technical questions. The initial questions had to do with some of my previous work experience and the algorithms and design approaches I used to solve problems.

The final question (and the one that stumped me) had to do with the implementation of a text autocompletion system. No matter what position you're interviewing for, I would make sure that you have brushed up on some fundamental data structures.

The iPhone has a feature that, when a user begins to enter a contact's name or email address, builds a list of possible matches. How would you implement this so the search performs quickly and changes each time a user inputs a character?