0

A cellular phone company is going to launch new model of an existing smart phone having maximum of 2 gigabytes memory. Being a programmer, you are given a task to develop application for better utilization of its phone book resource.

You should keep in mind the fact that a single contact can be stored as “First Name”, “Last Name” and “phone number” in alphabetical order. With the passage of time phone book updates as new contact comes or removed from the phone book.

Following are two factors which you must keep in mind while performing the required task.

Space limitations, as you know the available space is limited.Time required for accessing a particular contact, which must not exceed a given threshold.

As a programmer, which data structure will you use to perform the said task, provide proper reasons to support your answer?

2 Answers 2

1

I will use trie.

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree. In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a tree-shaped deterministic finite automaton. Each finite language is generated by a trie automaton, and each trie can be compressed into a deterministic acyclic finite state automaton.

Image of trie from Wikipedia page

Image of trie from Wikipedia page

A trie has a number of advantages over binary search trees.A trie can also be used to replace a hash table, over which it has the following advantages:

  1. Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.
  2. There is no need to provide a hash function or to change hash functions as more keys are added to a trie.
  3. A trie can provide an alphabetical ordering of the entries by key.

According to Wikipedia page, Trie is a well-suited data structure for representing Predictive Text or Autocomplete dictionary. For storing the phone numbers, we just need to add an additional node at the end of the trie which contains the phone number. Also, we need to build another trie for storing the numbers. In this case, instead of letters, number become a node in the trie. The last node, that is leaf node contains the name of the person who owns that number. By using these two tries, we can easily implement phone book. And we can search with respect to the number and/or name of the person.

A Paragraph from Wikipedia article:

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries

0

I'm not very experienced in programming, but I think that Hashing with Chaining could be an appropriate method to follow for the phonebook. I believe that this kind of structure covers all the requirements you asked for.

  1. It allocates only the memory it needs for the data to store plus the pointers for the next node as it is implemented by using dynamically allocated nodes in linked lists.
  2. Search, insertion and deletion all have O(n) worst case. More often 0(hash(x)).
  3. If you hash the elements by the first letter of the Last name you can gain some sorting time. You will get 26 lists (if all first names begin with letters) which you will need to sort. And Linked Lists have O(n logn) worst case.

I hope i didn't mess up with my answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.