i have a one idea in my mind is to implement a hash table structure based on 26 alphabets and a data structure of words. struct word { int info; char a[n]; }; structure contains the info about the word and an array in which document it is present or not out of n ex if it is word is mnnit and it is in document 1 ,4,6,9 the info of the structure would be char[1,4,6,9]=1 and the rest are zero. insertion of word would take o(1) time but searching would take o(n) time if list is implemented as an array list and if implemented as an binary search tree would take it log(n) but than insertion would also take log(n) time
On Mon, Dec 13, 2010 at 9:55 PM, GOBIND KUMAR <gobind....@gmail.com> wrote: > One of my friends attended google interview.This was one the question > asked. > > "you are given N documents(possibly in millions) with words in them. > design datastructures such that the following scenarios take optimal time: > > a. print all the the docs having a given word > > b. print the docs having both of 2 given words" > > > Help me in solving this problem. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.