Design Phone Book

Designa a phone book - basically contact book on phone.
Give data structures and give time complexity to search a phone number.
Ex: search - freeninza and if found in your phone book return the mobile number of user.

http://www.programcreek.com/2014/08/leetcode-design-phone-directory-java/

Strategy:

Using a Trie can help you on that and the time will be O(L) where L is the string length.
1) input name and find phone number
-- Trie structure for name (string), phone number as assocaited value.
-- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2) input phone number and find name
-- hash table
(phone number is unique, so use as hash key)

The great thing about a trie is that it would provide functionality to easily facilitate partial searches, you type in the start of the persons name or phone number and you could return all leaf nodes that match that that prefix. Insertion and search will take O(length of phone number). To display the numbers starting with one or more digits, then the complexity will be the O(prefix length)+O(number of children for the immediate prefix node * length of the remaining number from child nodes).

Question 2
--------------
All the phones stores contacts in some way. Primitive phones has less memory and less processing power. So design a data structure which stores the contacts. This should use as less memory as possible and support the algorithm to run efficiently. Basic operations on this data structure is given a number, how to lookup contact name and vice versa.

http://www.geeksforgeeks.org/mircosoft-interview-14/

What are the differences between a hash table and a binary search tree? Suppose that you are trying to figure out which of those data structures to use when designing the address book for a cell phone that has limited memory. Which data structure would you use?

A hash table can insert and retrieve elements in O(1) (for a big-O refresher read here). A binary search tree can insert and retrieve elements in O(log(n)), which is quite a bit slower than the hash table which can do it in O(1).

A hash table is an unordered data structure

When designing a cell phone, you want to keep as much data as possible available for data storage. A hash table is an unordered data structure – which means that it does not keep its elements in any particular order. So, if you use a hash table for a cell phone address book, then you would need additional memory to sort the values because you would definitely need to display the values in alphabetical order – it is an address book after all. So, by using a hash table you have to set aside memory to sort elements that would have otherwise be used as storage space.

A binary search tree is a sorted data structure

Because a binary search tree is already sorted, there will be no need to waste memory or processing time sorting records in a cell phone. As we mentioned earlier, doing a lookup or an insert on a binary tree is slower than doing it with a hash table, but a cell phone address book will almost never have more than 5,000 entries. With such a small number of entries, a binary search tree’s O(log(n)) will definitely be fast enough. So, given all that information, a binary search tree is the data structure that you should use in this scenario, since it is a better choice than a hash table.