Implement phone directory using two tries

Question

    I have encountered an interview question
    “Implement a phone directory using Data Structures”                

I want to solve it using tries.By solving it with tries,I tried using two tries,one for name and another for phone number, but I faced a difficulty .
Suppose ,I have to add three entries( AB “112” BC ”124” CD ”225”) Then if I query the name for number “225”,how do I return CD. that is,how these two tries will be linked .

    One approach I was thinking was taking two pointers in both the tries.
    These pointers will point to the first and last word in the other trie.
    For example,if the structures are as follows:

    Struct nametrie                            
    {                                                       
     Struct nametrie *child[26];
     struct phonetrie*head,*tail;
     struct phonetrie*root;       

     -----------    
    }                                                       

      Struct phonetrie
     {
             struct phonetrie*child[9];
             struct nametrie*head,*tail;
             struct nametrie*root;
        ----------- 
      }


    Then for AB “112”,  
    Name trie willstore head(1) and tail (2).

But I think this approach will not work for duplicate entries(one name and multiple numbers.)

Can someone please explain a good approach.I am not looking for code but good understanding of approach,may be via diagram or algorithm.

Answer 1

I dont know C so I cant comment in your code.

The idea of using tries is valid.

you seems to be missing what data the nodes can hold in tries

the node in trees has 2 main components

1. the data it has which can be anytype
2. list of childen (or left , right childeren) or any combination of children

what we will do here is that we will add another field to each node and call it the value "theValue"

So the trie node will look like this

Class TrieNode{
public char theChar;
public String theValue;
public List<TrieNode> children;
}

So for forward lookup (name to phone) you construct one Trie and on the node that match entry in the directory you will set theValue to that entrie.

you will need to create 2nd trie to do the same for reverse lookup (phone to name)

So to give you example how it will look like for this data it will be

( AB “112” AC ”124” ACD ”225”)

//create nodes
TrieNode root = new TrieNode();
TrieNode A = new TrieNode();
A.theChar = 'A';
TrieNode B = new TrieNode();
A.theChar = 'B';
TrieNode C = new TrieNode();
A.theChar = 'C';
TrieNode C2 = new TrieNode();
A.theChar = 'C';
TrieNode D = new TrieNode();
A.theChar = 'D';
//link nodes together
root.children = new ArrayList<>();
root.children.add(A);
A.children = new ArrayList<>();
A.children.add(B);
A.children.add(C);
B.children = new ArrayList<>();
B.children.add(C2);
//fill the data
B.theValue = "112";
C.theValue = "124";
C2.theValue = "225";

now you can easy traverse this Trie and when you reach a node and whant to check the value just read theValue

i hope it is clear