@sagar: you might have proposed a solution but it ever occured to you that
(ptr->next)->next means that you have gone through two diferent nodes. For
saving one comparison , we are doing lot of un necessary computations which
, IMHO is not good or feasible . Linked list are not made for searching
purpose, for that arrays were made.
On Tue, Jul 19, 2011 at 12:13 PM, sagar pareek <sagarpar...@gmail.com>wrote:
> 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.-Hidequotedtext -
>>>>> >
>>>>> > > >> - 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.
>
--
Ankur Khurana
Computer Science , 4th year
Netaji Subhas Institute Of Technology
Delhi.
--
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.
