@Rahul rope data structure wont be a good idea...
Performance Operation Rope String(Array) index O(log n) O(1) split O(log n) O(1) concatenate O(log n) O(n) insert O(log n) O(n) delete O(log n) O(n) report O(log n) O(1) build O(n) O(n) the question says "data structure used should store and fetch data in efficient manner." but we would never be retrieving the partial url (a part of the url) On Friday, 18 May 2012 16:33:48 UTC+5:30, rahul r. srivastava wrote: > > rope data structure can be gud in such cases...... hashing may not be too > efficient as many url wud almost be same as mentioned by prakash..... trie > is another option but i believe overhead in trie will be more....... > correct me if i am wrong..... > > On Fri, May 18, 2012 at 11:33 AM, Ashish Goel <[email protected]> wrote: > >> Tiger Tree Hash >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> >> On Thu, May 17, 2012 at 11:16 PM, Prem Krishna Chettri < >> [email protected]> wrote: >> >>> For the cases where Storing the Value is the only Concern and (Not the >>> Retrieval efficiency), I would Suggest Something called DFA Subset >>> minimization.. Google for it ... and after the final subset as said U can >>> use something called DAWG for the most Most Optimal solution.. >>> >>> >>> On Thu, May 17, 2012 at 2:58 PM, Prakash D <[email protected]> wrote: >>> >>>> We can still improve this trie idea.. >>>> >>>> say we have urls like >>>> www.google.com >>>> www.goodbye.com >>>> www.google.com/transliterate >>>> www.goodstrain.com/good >>>> >>>> we can subdivide everything under "www.goo" >>>> I mean we can store each character as a node in a trie and call it >>>> like a "URL dictionary" >>>> >>>> >>>> On Wed, May 16, 2012 at 5:43 PM, omega9 <[email protected]> >>>> wrote: >>>> > >>>> > >>>> > On May 16, 10:33 am, atul anand <[email protected]> wrote: >>>> >> @amit : >>>> >> >>>> >> here is the reason :- >>>> >> >>>> >> each url sayhttp://www.geeksforgeeks.org >>>> >> >>>> >> you will hash following urlshttp://www.geeksforgeeks.orghttp:// >>>> www.geeksforgeeks.org/archiveshttp://www.geeksforgeeks.org/archives/19248http://www.geeksforgeeks.org/archives/1111http://www.geeksforgeeks.org/archives/19221http://www.geeksforgeeks.org/archives/19290http://www.geeksforgeeks.org/archives/1876http://www.geeksforgeeks.org/archives/1763 >>>> >> >>>> >> "http://www.geeksforgeeks.org"; is the redundant part in each url >>>> ..... it >>>> >> would unnecessary m/m to save all URLs. >>>> >> >>>> >> ok now say file have 20 million urls ..... .....now what would you >>>> do.?? >>>> >> >>>> > >>>> > I think the trie suggestion was good. Have each domain (with the >>>> > protocol part) as a node and then have the subsequent directory >>>> > locations as a hierarchy under it. >>>> > >>>> > -- >>>> > You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> > To post to this group, send email to [email protected]. >>>> > To unsubscribe from this group, send email to >>>> [email protected]. >>>> > For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> > >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_MFEHEH3cSUJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
