hey check my algo...i mentioned all the possible cases :) On Tue, Jul 19, 2011 at 11:31 AM, oppilas . <jatka.oppimi...@gmail.com>wrote:
> Yes we can avoid integer comparison. > > But for jumping we will need to check whether the next node is null or > not. > So, depending upon the jump size, the number of comparison in worst case > can be very large if our jump size is increasing exponentially. So, why not > just compare with the next node instead of jumping. > > > > On Tue, Jul 19, 2011 at 10:47 AM, sunny agrawal > <sunny816.i...@gmail.com>wrote: > >> yes Alok u r right that in any case we will traverse k times if k is the >> position if the element that need to searched >> but by jumping we can save the time of avoiding unnecessary comparisions >> >> >> >> On Tue, Jul 19, 2011 at 10:44 AM, Alok Prakash <alok251...@gmail.com>wrote: >> >>> >>> If i am not wrong, in a linked list to move to any number of position, >>> say n, we have to traverse all intermediate nodes of the linked list. >>> >>> So, it does not matter if we are moving pointer by 2,4,8,... positions, >>> we have to scan all intermediate nodes. >>> >>> Is it not a simple searching???? >>> >>> >>> >>> On Tue, Jul 19, 2011 at 9:17 AM, sumit <sumitispar...@gmail.com> wrote: >>> >>>> Here is the idea I was thinking of: >>>> >>>> - start from the root: if(root->data < k) move to position 2 in the >>>> list. >>>> - in this way every time move the pointer to the position double the >>>> current position and compare th eelement of node with k( moving here >>>> is form 1 - 2 , 2-4, 4-8 ,8-16 ......) >>>> - suppose you found a certain node at position n whose node->data > >>>> k , then now u only have to search for k between index n/2 to n (i.e. >>>> if you found 16th element >k then search for k between 8th and 16ht >>>> element).. >>>> >>>> correct me if any flaws..... >>>> >>>> On Jul 19, 3:38 am, Dumanshu <duman...@gmail.com> wrote: >>>> > @Gaurav: Ever Increasing means that you don't know the length of the >>>> > list. So you have to assume some index n, traverse the list upto that >>>> > point and check the results. If not found increment the n to some >>>> > higher value. >>>> > We are basically trying to improve the complexity by taking higher and >>>> > higher jumps for n. >>>> > >>>> > On Jul 19, 2:03 am, Gaurav Popli <abeygau...@gmail.com> wrote: >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > > yeah...im saying to reach position n at which k is placed we have to >>>> > > trverse n positions from head or not...?? >>>> > > and i didnt understand the use of ever increasing...please elaborate >>>> on it.. >>>> > >>>> > > On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu <duman...@gmail.com> >>>> wrote: >>>> > > > @Swathi: plz give the TC of ur algo (exponential plus log) >>>> > >>>> > > > On Jul 18, 10:14 pm, Swathi <chukka.swa...@gmail.com> wrote: >>>> > > >> The solution to this problem will be a combination of exponential >>>> increase >>>> > > >> and the binary search.. >>>> > >>>> > > >> start = 0; >>>> > > >> end = 0; >>>> > > >> index =0; >>>> > > >> middle = 0; >>>> > > >> while (1) >>>> > > >> { >>>> > > >> if(a[start] == data) >>>> > > >> return start; >>>> > > >> if(a[end] == data) >>>> > > >> return end; >>>> > > >> if(data > end) >>>> > > >> { >>>> > > >> start = end; >>>> > > >> end = pow(start,2); // here we are consider exponential for >>>> faster >>>> > > >> search. >>>> > > >> // no need to check any boundary conditions as the array is >>>> infinite >>>> > > >> continue; >>>> > > >> } >>>> > > >> else >>>> > > >> { >>>> > > >> // do binary search between start index and end index because >>>> data is >>>> > > >> inbetween a[start] and a[end] >>>> > > >> } >>>> > >>>> > > >> } >>>> > >>>> > > >> Hope this helps... >>>> > >>>> > > >> On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli < >>>> gpgaurav.n...@gmail.com>wrote: >>>> > >>>> > > >> > i dont understand it..if k is at position an let suppose....so >>>> to >>>> > > >> > check at that position dont you have to traverse till that >>>> position >>>> > > >> > ...is thr anything else than the head of list...??or i >>>> understood >>>> > > >> > wrongly...?? >>>> > >>>> > > >> > On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek < >>>> sagarpar...@gmail.com> >>>> > > >> > wrote: >>>> > > >> > > Update on 2nd line >>>> > >>>> > > >> > > 2. if( ptr2=ptr1->next->next.......(5 or 10 times) ) goto >>>> 3. >>>> > > >> > else >>>> > > >> > > make linear search till NULL encounter and exit with the >>>> solution >>>> > >>>> > > >> > > On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek < >>>> sagarpar...@gmail.com> >>>> > > >> > wrote: >>>> > >>>> > > >> > >> i have one approach :- >>>> > >>>> > > >> > >> first compare root->data and k >>>> > > >> > >> if k is very much greater than root->data then set >>>> next=5or10 ur choice >>>> > >>>> > > >> > >> else set next 2or3 ur choice >>>> > > >> > >> take two pointers ptr1 and ptr2 >>>> > >>>> > > >> > >> now lets take k is much greater than root->data >>>> > > >> > >> then >>>> > > >> > >> 1. set ptr1=root //initially >>>> > > >> > >> 2. if( ptr2=ptr1->next->next.......(5 or 10 times) ) else >>>> make linear >>>> > > >> > >> search till NULL encounter >>>> > > >> > >> 3. if ptr2->data==k return its position >>>> > > >> > >> 4. else if (ptr2->data>k) set ptr1=ptr2 goto 2 >>>> > > >> > >> 5. else traverse the ptr1 upto ptr2, if found return its >>>> position else >>>> > > >> > >> return fail >>>> > >>>> > > >> > >> if anyone has more efficient solution then pls tell :) >>>> > > >> > >> On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu < >>>> duman...@gmail.com> wrote: >>>> > >>>> > > >> > >>> You have a sorted linked list of integers of some length >>>> you don't >>>> > > >> > >>> know and it keeps on increasing. You are given a number k. >>>> Print the >>>> > > >> > >>> position of the number k. >>>> > > >> > >>> Basically, you have to search for number k in the ever >>>> growing sorted >>>> > > >> > >>> list and print its position. >>>> > >>>> > > >> > >>> Please write the complexity of whatever solution you >>>> propose. >>>> > >>>> > > >> > >>> -- >>>> > > >> > >>> 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. >>>> > >>>> > > >> > -- >>>> > > >> > 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.-Hidequoted text >>>> - >>>> > >>>> > > >> - Show quoted text - >>>> > >>>> > > > -- >>>> > > > 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 athttp:// >>>> groups.google.com/group/algogeeks?hl=en.-Hide quoted text - >>>> > >>>> > > - Show quoted text - >>>> >>>> -- >>>> 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 >>> Alok Prakash >>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Sunny Aggrawal >> B-Tech IV year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> 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. >> > > -- > 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 -- 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.