CareerCup

Store the Name-Number pair in a Hash, with the number as key.
HashTable must be implemented in a separate chaining strategy, storing all the matching names in a list, against the key (phone number)

Store the Name-Number pair in a Hash, with the number as key.
HashTable must be implemented in a separate chaining strategy, storing all the matching names in a list, against the key (phone number)

Store the Name-Number pair in a Hash, with the number as key.
HashTable must be implemented in a separate chaining strategy, storing all the matching names in a list, against the key (phone number)

Is a database forbidden? That's the "right" approach. If you couldn't use a database server, then SQLite (ha ha ha). Ok, pure data structures then:

You'd need a series of data structures.

1.) hash table/map of primary-key to data (name, phone number, address perhaps).
2.) Associative containers for each one of the attributes that youd want to search on.
2.1) Suffix array to support searching. Value would be lists of associated keys of data. (Joh would link to all Johns, Johnathan, Johnny, etc)
2.2) You could stick the phone numbers, and addresses, and all data in here as well, to support the searching functionality.

HashSet with equals method overridden to compare numbers if sufficient.

hasmap of type <str (for name), hashset<int> (for phone numbers)>?

in Java : Hashmap<String,ArrayList<String>> would give something like this:

["John Smith": '555-5500', '555-5501', '555-5502']

I stored the phone numbers as strings, but you should ask the interviewer if you should consider a phone number as an Integer or String. Always ask to clarify the requirements before diving into code :)

You can construct Trie. Each node which represent the last letter for the name may have List<String> which stores numbers for given name.
Additional benefits for this solution are:
1) Sorting of phone book is very easy by only pre-order traversal of the trie
2) Finding names which matches given prefix