No reasons, the structure is static so sorted array is the fastest way. Don't know how about trie, it's hard to estimate...
On 9 нояб, 18:16, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
