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.- 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.
>
>
--
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.
