CareerCup

Although hash map would give you the fastest lookup, I think the right data structure here is a trie. This is so because when you type Jo, we want to list
Joana
Joe
John
Joseph
.....

hash Map only works when complete key is given....trie works even in partial key or incomplete key...
like if you have following enteries
Joe
John

then searching for jo will return you nothing in hashmap but in trie you will get all possible combination

Trie can also be optimized by not having nodes with degree==2, merged into single node.

As we always want our phonebook to be sorted in mobile. Binary Search Tree would be the best options. Like we save some memory of sorting when user queries for the result.

How will one store in a BST???
Also order can be maintained in a trie as well.

Trie is much efficient for this problem. Names can be stored in trie with the phone numbers as satellite data at the end of names. An even better ds will be ternary search tree, it saves memory as compared to trie. So for very large phone book, ternary search tree will give best efficiency.

Patricia tree is the ideal trie DS for any kind of string operation. It uses bit index based on the difference in bits on new string with existing string and stores the new string in the differential index. This results in natural compression of trie nodes resulting in efficient search operation which is what is needed for Phone note book.

An easier but not so efficient ds is building tree with alphabet as index.

typedef struct trie_ {
struct trie_ *alpha[MAX_ALPH];
bool leaf;
} trie_td;