Desigin Contact Book

Designing a PhoneBook application where each Contact includes :

FirstName

LastName

Mobile Number

What is required?

      

      a)      Searching Mobile Number using FirstName

      b)     Searching Mobile Number using LastName

      c)      Searching FirstName and LastName using Mobile Number

Let’s think what possible Data structure we’ve which might work out for designing PhoneBook

      a)      HashMap – Everyone might think that HashMap is the easiest one to use when it comes to implementation but in real time, there is lot of bottle neck cases where using HashMap proves huge wastage of space.

Example:  If you want to use first name as the key, then only searching by first name will be fast. If you want all three of them to be fast, then it takes a lot of space as you have to build these data structures for all three of them separately.

Also making Phonebook searching to work as auto-complete suggestions is a basic necessity and making HashMap to take care of this would take humungous space.

     b)     Trie- Trie can help you on that the Insertion and Lookup time will be O(Length of      String)  Input name and Find Phone Number. Trie Structure will be name (string), phone number as Associated value.

The great thing about a Trie is that it would provide functionality to easily facilitate partial searches, You type in the start of the Person’s name or Phone number and you could Get all names that start with that Word. The Leaf Node will contain the Phone Numbers Associated with the Contact Name.

Example: Storing Paras Chawla as a contact with mobile number -9717364987

Bottle neck cases

When user try to search ‘Paras’ or ‘Chawla’ or ‘Paras Chawla’ or ‘Chawla Paras’,

 Suggestions, all combinations has to show number 9717364987

Lets see how to implement using Trie Data structure :

public class ContactManagement {

    private final ContactNode root;

    HashMap<Long, Contact> map = new HashMap<>();

    public ContactManagement() {

         root = new ContactNode();

    }

    public static void main(String[] args) {

         ContactManagement trie = new ContactManagement();

         List<Contact> list = new ArrayList<>();

         Contact contact1 = new Contact("Paras", "Chawla", 9717364);

         Contact contact2 = new Contact("Sonal", "Gupta", 9873774);

         Contact contact3 = new Contact("Richa", "Chawla", 9990100);

         list.add(contact1);

         list.add(contact2);

         list.add(contact3);

         for (int i = 0; i < list.size(); i++)

             trie.insert(list.get(i).getFirstName(), list.get(i).getMobileNumber());

         String[] wholeWordSearchStr = { "Paras", "Sonal", "Richa", "Unknown" };

         for (String fName : wholeWordSearchStr) {

             System.out.println("Get Mobile number 

             for Name " + fName + " Mobile Number -->" 

             + trie.searchMobileNumber(fName));

         }

    }

    public void insert(String firstName, long mobileNumber) {

         ContactNode current = root;

         for (int i = 0; i < firstName.length(); i++) {

             char ch = firstName.charAt(i);

             ContactNode node = current.children.get(ch);

             if (node == null) {

                 node = new ContactNode();

                 current.children.put(ch, node);

             }

             current = node;

         }

         current.eow = true;

         current.mobileNumber = mobileNumber;

         System.out.println("Contact inserted successfully!!");

    }

    public long searchMobileNumber(String firstName) {

         ContactNode current = root;

         for (int i = 0; i < firstName.length(); i++) {

             char ch = firstName.charAt(i);

             ContactNode childNode = current.children.get(ch);

             if (childNode == null)

                 return 0L;

             else

                 current = childNode;

         }

         if (current.eow)

             return current.mobileNumber;

         else

             return 0L;

    }

}

ContactNode acting as TrieNode

class ContactNode {

    boolean eow;

    long mobileNumber;

    Map<Character, ContactNode> children;

    public ContactNode() {

         eow = false;

         children = new HashMap<Character, ContactNode>();

    }

}

Contact as POJO class

public class Contact {

     String firstName;

     String lastName;

     long mobileNumber;

     public Contact(String firstName, String lastName, long mobileNumber) {

          super();

          this.firstName = firstName;

          this.lastName = lastName;

          this.mobileNumber = mobileNumber;

     }

     public String getFirstName() {

          return firstName;

     }

     public void setFirstName(String firstName) {

          this.firstName = firstName;

     }

     public String getLastName() {

          return lastName;

     }

     public void setLastName(String lastName) {

          this.lastName = lastName;

     }

     public long getMobileNumber() {

          return mobileNumber;

     }

     public void setMobileNumber(long mobileNumber) {

          this.mobileNumber = mobileNumber;

     }

}

Output

Contact inserted successfully!!

Contact inserted successfully!!

Contact inserted successfully!!

Get Mobile number for Name Paras Mobile Number -->9717364

Get Mobile number for Name Sonal Mobile Number -->9873774

Get Mobile number for Name Richa Mobile Number -->9990100

Get Mobile number for Name Unknown Mobile Number -->0