which data structure to use to implement phone book which can be searched either on Name or phone number?

Question

pl suggest an appropriate data structure to implement a phone dictionary, which merely has person Name and phone number. I could think of using hashtable having name as key and phone number as value.

But the problem is we can't search for a person name given his phone number. This can be assumed that all names are unique.

~Ashish

Answer 1

Probably a data structure consisting of a pair of tries might work well. One trie would give you a phone numbers given a name, and the other would give you names given a phone number.

The nodes of the tree which gives you phone numbers for a name would have edges labeled with symbols making up the name. The value associated with each vertex would be pointer to a node in the other trie (the one that gives you names for phone numbers) corresponding to the phone number of the person whose name leads from the root to the vertex. Given a name, you can thus return the corresponding phone number of the person with that name (by traversing from the linked node to the root). In fact, you could use this to find all people whose names begin with a certain prefix and their corresponding phone numbers.

Here's an example of the name-to-phone number trie:

  J    A    C    K
1--->2--->3--->4--->5
     |    |
   I |  S V 
     |    9--->10--->11
     V      O     N
     6--->7--->8
       L    L

Suppose the people represented are Jack, Jill, Jason and Jaso (a foreign exchange student). The other trie might look like this:

  1    2    3
A--->B--->C--->D
     |    |
   3 |    V 2
     |    E
     V 3
     F--->G
     |
   2 |
     V
     H

The phone numbers are 123, 122, 133 and 132.

Now, the references will look like this:

Name Trie    Number Trie
---------    -----------
1->null      A->null
2->null      B->null
3->null      C->null
4->null      D->10
5->E         E->5
6->null      F->null
7->null      G->8
8->G         H->11
9->null
10->D
11->H

Upon input JAS to the name trie, we can determine easily that there are no numbers for this name since node 9 has no corresponding number. Suppose we want to list all numbers for people whose name starts thusly. We can traverse the tree using whatever method you like (an inorder traversal based on alphabetical order would seem sane) gives JASO (10) and JASON (11) which we see do have corresponding nodes in the phone number trie.

For each of these nodes, we can jump to the phone numbers trie and work our way back up to the parent (assuming we saved the parent reference in each node, which is doable). Along the way, we can keep track of the edge labels to derive the number corresponding to our node. Since 10->D, we find C, B and A on the way back to the root A and the digits along the way were 3, 2 and 1. By concatenating them in the order seen during backtracking, and subsequently reversing that concatenation, we obtain the string that leads from A to D, thus the one corresponding to JASO: 123. Similarly for JASON.

Adding a new entry means simultaneously adding an entry to both tries, and then linking them. If duplicate names or numbers are allowed, then instead of pointing to one node in the other trie, a collection of nodes could be referenced. Removing an entry means simply removing the corresponding node from each tree. Valid names are ones with phone numbers referenced. Valid phone numbers are ones with names referenced.

Answer 2

If you want to go through the names quickly, You can implement Tries.

Tries are basically trees in which each node is connected to n children, where n is the number of characters you can think of (can be 26 for only small characters in search string, 52 if you consider capital and small letters differently or 62 if you bring numbers into the indexing too, all based on your requirement of Trie).

More information can be found here.

A sample implementation of trie can be found here:

Tries are used effectively to do partial string searches.

The search and insert complexity is limited to the length of the word being searched O(length).

Answer 3

Use Gauva Bimap and get inverted of it.

BiMap<Integer, String> biMap = HashBiMap.create(); biMap.put(9856435634, "M"); biMap.put(9856435635, "S"); biMap.put(9856435636, "R");  System.out.println(biMap.inverse().get("M")); 

Answer 4

Choosing a data structure depends on the available resources, which are time and space (Processor and memory), in our time hardware with high specs is major, so if you target good specs, I suggest you make things simple by implementing a linked list, with each node contains the name and the number, then you implement two functions one for searching using name, and one for the number, also you can sort names to use binary search in case of searching for names.

Note that the Worst case for Access and Search for linked lists is O(n) for time and O(n) for space, which is fairly good for good specs hardware, for further details on time and space complexity for common data structures see this Link in order to compare and choose a proper one for your requirements.