CareerCup

Hmm...looks like the previous answers went a little details in terms of the data structures to use. I'm not sure if I should answer this in a high level scope or low level, but here's my answer.
1. Simple UI. Smart phones are small, you cannot have a UI that requires a lot of micro control such as pressing a tiny buttons or icons. This will make people press the wrong things and can be frustrating easily.
2. (A question for the interviewer, is it a casual social network like Facebook or a professional one like LinkedIn). If it is a casual one then it needs a "wow" factor that a compete with other competitors such as Facebook. The one I could think of is a feature that shows who's around you. Of course it needs to have the users permission first. (Sorta like Google Latitude)
3. Link local contacts to the app. Add those people that are stored locally to the network. This can save a lot of time and prevent users from searching/ adding them one by one.
4. Ability to instantly upload picture or videos. It is a must for social network applications.
5. Security. This one is also important. It needs to have a secure way to delete/ prevent people from hacking the account since people can lose their phone easily or letting others borrow their phones.

DESIGN:

(1)use phone number as user id which is unique
use trie datastructure to create, search and delete the user account
(2)end of each phone number in trie structure pointing to a structure node, which may have the important data like password(for login check), pointer to the main user data(like name, address, friends etc)
(3)the friends which are registered in the site and in contact list of user, store them as linked list where data is the pointer to the user srtuctre of there freinds
(4)make simple linked list implementation for sms, mms, files, ringtones, mp3 etc etc

(1)phone number and user details
(2)sms, mms sending
(3)contacts updates
(4)sharing contacts and searching conatcts
(5)file transfer, software updates, ringtones, mp3 etc