Amazon Interview Question Software Engineer / Developers
First , the structure of a node in a trie
struct Node {
char c;
struct Node *next[26];
};
Have a constructor which initialises next[i] = NULL, for 0<=i<26
Node* Insert(Node *root, string s) {
Node *p = root; //save root pointer
for(i=0,n=s.size();i<n;i++) {
if(root->c!=s[i]) break;
else {
root = root->next[s[i]-'a'];
}
}
if(i<n) {
while(i<n) {
Node *temp = (Node*) malloc(sizeof(Node));
temp->c = s[i];
root->next[s[i]-'a'] = temp;
root = temp;
}
return root=p;
}
I would say a linked list(with all names in sorted order) and a trie (of all names).
Lookup is a frequent operation in a phone book while insert is not so frequent. This explains the choice of the data structures.
Also, the trie will help in providing the user with suggestions when he starts searching by typing the first few characters of a name.
Hash is only good for static phonebook.
Use balanced search tree if you want to implement dynamic phonebook. AVL tree or red-black tree is a good option. They provide O(logn) gurantees on insert and delete
I think trie ( in compressed form) is the best choice for this type of questions. Coz as we all agree that phone-book's main operation is search : which can be done in O(m) time in a trie and easy updation , more importantly this time complexity is independent of the nodes and strings in them like in balanced trees which takes O(mlog n) time.
hash is not a good choice specifically for "phone" apps. You would want the items to be displayed sorted for which you need extra space when you have information in a hash table. A tree is certainly a better option
- PL April 03, 2010