Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-20 Thread Gaurav Popli
i want to ask one thing...the way some are saying first check with 2
then 4 and then 16to reach at that place we are suppose to
traverse it and also hav eto put a condition say like countn or
something...in this case also we are comparing so whats the
usecorrect me if im wrong.

On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com wrote:
 can be done in O(n) find tow nodes from starting position find two
 nodes p,q such that p  k  k  q as linked list is sorted we have to
 keep going on in right direction complexity will no less then O(N) as
 its linked list there is no notion of binary search sorted linked list
 think out why ?

 only think we can apply some logic to reduce the comparisons that's i
 also think will be gr8 improvement but approach sounds good if start
 comparing the nodes value using multiple of 2 fact .e.g. take an
 integer i=2^j  from j=0 to start comparing 2^0th node, 2^1th node,
 2^2th node2^jth node might be we are able to reduce the number of
 comparisons

 do notify me via gmail if i am wrong if u find difficulty in TC ? else
 happy learning

 if this would have been sorted array then we could have been solved it
 O(logn) suing same approach.


 Thanks
 Shashank Mani
 Computer Science
 Birla Institute of Technology, Mesra

 --
 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] Re: Ever growing sorted linked list

2011-07-20 Thread Pankaj
 One a not so standard way of doing that is while creating the link list,
keep an extra pointer in the node to point to the jump location.
Just hold the previous node in a temp say address of 2 node and when i/p
reaches 4, point the jumper pointer to 4 and make 4 the next jumper pointer.



On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:

 @Popli : Bingo , that is what i was thinking and mentioned in my previous
 post..


 On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli abeygau...@gmail.comwrote:

 i want to ask one thing...the way some are saying first check with 2
 then 4 and then 16to reach at that place we are suppose to
 traverse it and also hav eto put a condition say like countn or
 something...in this case also we are comparing so whats the
 usecorrect me if im wrong.

 On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com
 wrote:
  can be done in O(n) find tow nodes from starting position find two
  nodes p,q such that p  k  k  q as linked list is sorted we have to
  keep going on in right direction complexity will no less then O(N) as
  its linked list there is no notion of binary search sorted linked list
  think out why ?
 
  only think we can apply some logic to reduce the comparisons that's i
  also think will be gr8 improvement but approach sounds good if start
  comparing the nodes value using multiple of 2 fact .e.g. take an
  integer i=2^j  from j=0 to start comparing 2^0th node, 2^1th node,
  2^2th node2^jth node might be we are able to reduce the number of
  comparisons
 
  do notify me via gmail if i am wrong if u find difficulty in TC ? else
  happy learning
 
  if this would have been sorted array then we could have been solved it
  O(logn) suing same approach.
 
 
  Thanks
  Shashank Mani
  Computer Science
  Birla Institute of Technology, Mesra
 
  --
  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.




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


-- 
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] Re: Ever growing sorted linked list

2011-07-20 Thread saurabh singh
I think the novelty of this is that we are avoiding the comparison of new
element with all the members of data in LL

On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote:

 @Popli : Bingo , that is what i was thinking and mentioned in my previous
 post..


 On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli abeygau...@gmail.comwrote:

 i want to ask one thing...the way some are saying first check with 2
 then 4 and then 16to reach at that place we are suppose to
 traverse it and also hav eto put a condition say like countn or
 something...in this case also we are comparing so whats the
 usecorrect me if im wrong.

 On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com
 wrote:
  can be done in O(n) find tow nodes from starting position find two
  nodes p,q such that p  k  k  q as linked list is sorted we have to
  keep going on in right direction complexity will no less then O(N) as
  its linked list there is no notion of binary search sorted linked list
  think out why ?
 
  only think we can apply some logic to reduce the comparisons that's i
  also think will be gr8 improvement but approach sounds good if start
  comparing the nodes value using multiple of 2 fact .e.g. take an
  integer i=2^j  from j=0 to start comparing 2^0th node, 2^1th node,
  2^2th node2^jth node might be we are able to reduce the number of
  comparisons
 
  do notify me via gmail if i am wrong if u find difficulty in TC ? else
  happy learning
 
  if this would have been sorted array then we could have been solved it
  O(logn) suing same approach.
 
 
  Thanks
  Shashank Mani
  Computer Science
  Birla Institute of Technology, Mesra
 
  --
  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.




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




-- 
Thanks  Regards,
Saurabh

-- 
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] Re: Ever growing sorted linked list

2011-07-19 Thread sagar pareek
hey
check my algo...i mentioned all the possible cases   :)

On Tue, Jul 19, 2011 at 11:31 AM, oppilas . jatka.oppimi...@gmail.comwrote:

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

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


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

Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-18 Thread Gaurav Popli
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.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.- 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.



Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-18 Thread Alok Prakash
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.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 

Re: [algogeeks] Re: Ever growing sorted linked list

2011-07-18 Thread sunny agrawal
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.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