How about using a Red-Black tree ? On 11/9/07, Andrey <[EMAIL PROTECTED]> wrote: > > > I thought about trie first but then I've change my mind and decided > that I'd rater use a simple binary tree or even an sorted array. > > As we have quite limited set of first names and surnames we can easily > index them i.e. store them in sorted array and use an index in the > array indead of the entire name/surname (the array like this can also > be easily compressed). > Then we store pairs (surname_index, name_index) in sorted array and > perform binary search by request. > > The complexity will be. > log(S) - to find the index of surname where S is number of > different surnames > + > log(N) - to find the index of name where N is number of different > names > + > log(10 000 000) - to find pair (surname_index, name_index) > > The memory consumption estimate is clear. > > > Can you estimate complexity and memory consmption of trie? That would > be interesting!!! > > > > On Nov 9, 2:59 pm, "Varun S V" <[EMAIL PROTECTED]> wrote: > > I was asked the same question in my google interview!! The best > > solution for this is to use the TRIE data structure!! > > > > Google TRIE data structure for more details. It also gives an > > optimized search complexity. > > > > On Nov 8, 2007 11:40 AM, Rajat Gogri <[EMAIL PROTECTED]> wrote: > > > > > > > > > If you have to implement a phone book of 10 millin people in NYC, what > > > data structure would you use and why ? > > > Show the implementation if HashTable or Binary Trees? > > > > > Thanks, > > > Raj > > > > >
-- Ciao, Ajinkya --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
