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.
