Re: [algogeeks] Ever growing sorted linked list
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-datak) 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.
Re: [algogeeks] Ever growing sorted linked list
i dont understand it..if k is at position an let supposeso 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-datak) 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.
Re: [algogeeks] Ever growing sorted linked list
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.comwrote:
i dont understand it..if k is at position an let supposeso 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-datak) 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.
--
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.
Re: [algogeeks] Ever growing sorted linked list
@Swathi
read it again its linked list.using binary search is very costly here
:)
@Gaurav
sorry i forget the position counter in my algo...
if ptr2=ptr1-nextnext 10 times do then increment counter by 10
mean we are skipping 10 positions at a time
and as it is listed that it is sorted then we can compare ptr2-data with
the k
if k is greater then ptr2-data we will traverse ptr1 upto ptr2 or
untill we find the solution and before doing this make counter-=10;
and then increase it by 1 after moving ptr1 by 1 position
Still have any doubt?
On Mon, Jul 18, 2011 at 10:44 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.comwrote:
i dont understand it..if k is at position an let supposeso 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-datak) 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.
--
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.
