I wonder why people have discarded the idea of Hash map here. Searching is obviously the most important task here and if we are to assume that names can be uniformly hashed over a table of 1000 rows with each row containing 1000 names each.
Further optimization can be achieved by having names stored in binary search tree for each row. (So it will take max 10 comparisons to search a name) (Need to Keep it a balanced tree) So in all, a total of max 11 operations - 1 Hash + 10 comparisons will be used to search for any phone number. In the above, hashing is to be done on names obviously. On Thu, Jun 30, 2011 at 12:24 PM, sagar pareek <sagarpar...@gmail.com> wrote: > Sorry for the previous post it got a mistake.... here take a look again :- > > In TRIE , we can store nodes by characters. So it is very easy to search by > names and hence their corresponding numbers :) . > TRIE saves a lot memory coz it stares a character only once. > > LIKE :- > if i want to save "sagar" with phone no. 123456789 then we store it in TRIE > as : > > s-NULL > | > a-NULL > | > g-NULL > | > a-NULL > | > r-123456789 > | > NULL > > now if we want to add new contact as sagarika,123454321 then it will stored > as :- > s-NULL > | > a-NULL > | > g-NULL > | > a-NULL > | > r-123456789 > | > i-NULL > | > k-NULL > | > a-123454321 > | > NULL > > now if we want to store new contact as sag,345678909 > > s-NULL > | > a-NULL > | > g-345678909 > | > a-NULL > | > r-123456789 > | > i-NULL > | > k-NULL > | > a- 123454321 > | > NULL > > I hope now you get how it saves a lot memory :) > > On Thu, Jun 30, 2011 at 12:21 PM, sagar pareek <sagarpar...@gmail.com> > wrote: >> >> In TRIE , we can store nodes by characters. So it is very easy to search >> by names and hence their corresponding numbers :) . >> TRIE saves a lot memory coz it stares a character only once. >> >> LIKE :- >> if i want to save "sagar" with phone no. 123456789 then we store it in >> TRIE as : >> >> s-NULL >> | >> a-NULL >> | >> g-NULL >> | >> a-NULL >> | >> r-123456789 >> | >> NULL >> >> now if we want to add new contact as sagarika,123454321 then it will >> stored as :- >> s-NULL >> | >> a-NULL >> | >> g-NULL >> | >> a-NULL >> | >> r-123456789 >> | >> i-NULL >> | >> k-NULL >> | >> NULL >> >> now if we want to store new contact as sag,345678909 >> >> s-NULL >> | >> a-NULL >> | >> g-345678909 >> | >> a-NULL >> | >> r-123456789 >> | >> i-NULL >> | >> k-NULL >> | >> NULL >> >> I hope now you get how it saves a lot memory :) >> | >> a- 123454321 >> >> On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal <ankitsamb...@gmail.com> >> wrote: >>> >>> @Swathi :We can't use trie data structure to store the phone numbers. >>> The most sound reason is that the users require phone numbers to be >>> sorted by name, but by using the trie data structure we can't get the >>> phone numbers which are sorted by name. Again we can't use trie whose >>> nodes are numbers, because phone numbers are searched by name always. >>> Nobody searches for a name, given a number. And if we use names as the >>> node in the trie, we end up using a lot of space because of pointers. >>> >>> Worst case time complexity of search using trie ----- O(n) >>> Worst case time complexity of search using fixed array with circular >>> indexing ---- O(log n) because we can use binary search, and search >>> is most frequent query in a list of phone numbers. >>> >>> I hope u got the idea. Another point is that we have very limited >>> memory in a phone, so we have too use fixed array. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Regards >> SAGAR PAREEK >> COMPUTER SCIENCE AND ENGINEERING >> NIT ALLAHABAD >> > > > > -- > Regards > SAGAR PAREEK > COMPUTER SCIENCE AND ENGINEERING > NIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- --Navneet -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
