Re: [algogeeks] Linked List question

2013-01-07 Thread Doom 
Thank you for the code snippet.

What I don't understand is 

if( (double)rand() / RAND_MAX <  1 / k ) 

Here, Why do we use less than inequality?

Why won't Udit's solution of just using the minimum random number work?

On Tuesday, 1 January 2013 20:57:47 UTC+5:30, Dave wrote:
>
> @Doom: Yes. It is necessary to go through the entire list. The code could 
> look like this:
>  
> int* p = head;
> int k = 1;
> while( head )
> {
> head = head -> next;
> k++;
> if( k * (double)rand() < RAND_MAX )
> p = head;
> }
>  
> Dave
>
> On Sunday, December 30, 2012 12:40:28 PM UTC-6, Doom wrote:
>
>> Hi Dave
>>
>> Please help me with some additional clarification regarding the 
>> implementation of this algo. How do we make use of random number generator?
>>
>> And is it necessary to traverse the list until the end? 
>>
>>
>> On Friday, 28 December 2012 19:35:07 UTC+5:30, Dave wrote:
>>>
>>> @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
>>> the kth node, set p to the kth node with probability 1/k. When you reach 
>>> the end of the list, return p, which will point to a random node with 
>>> uniform probability.
>>>  
>>> Dave
>>>
>>> On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
>>>
 i mean the length of the linked list is not known to us.
 @udit how can we do this in single traversal ? i think we need to 
 traverse the linked list twice in your case.
 Please reply if i am wrong ?

 On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal wrote:

> If the length of the linked is infinite then the above algo would do
> the needful.
> In case you have a finite length linked list, then you can normalize
> the random value using following:
> Suppose length of linked list is: l
> random number is: r; and r > l
> then new random number would be: r1 = r%l;
> now again use the above algo using new random number r1;
>
> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
> > You said : "Given a linked list of infinite length"
> >
> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
> >  wrote:
> >> But suppose a random number generate a value 5 and your linked list 
> has only
> >> four elements. In that case what would be the answer ???
> >>
> >>
> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
> hpre...@gmail.com>
> >> wrote:
> >>>
> >>> Well my algo will be Something like this
> >>>
> >>> 1> Get a Random number. Perhaps You can have the function like 
> Randon(List
> >>> *head, int Randomnumber)
> >>>
> >>> 2> Use the function argument Randomnumber to loop the list.
> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
> >>>head = head -> next;
> >>> }
> >>>
> >>> 3> print (head->value);
> >>>
> >>> 4> return ;
> >>>
> >>> Now as we are using byvalue when we return the value of head 
> remains the
> >>> same old head value. So everytime we call we are traversing the 
> same old
> >>> list.
> >>>
> >>>  The Random variable can be taken inside the function itself if 
> the user
> >>> is not taking the random value.
> >>>  i.e. int Randomnumber = random();  and now the user can calll 
> Simple
> >>> Random(head);
> >>>
> >>>
> >>>
> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
> >>>  wrote:
> 
>  random node
> >>>
> >>>
> >>> --
> >>>
> >>>
> >>
> >>
> >>
> >>
> >> --
> >> With Best Wishes
> >>
> >> From:
> >>
> >> Naveen Shukla
> >> IIIT Allahabad
> >> B.Tech IT 4th year
> >> Mob No: 07860896972
> >> E-mail naveenshukla...@gmail.com
> >>
> >> --
> >>
> >>
> >
> > --
> >
> >
>
>
>
> --
> Udit Agarwal
> B.Tech. ( Information Technology ) , 7th Semester,
> Indian Institute of Information Technology
> Allahabad - 211012, India
> Email : udit...@gmail.com
> Mobile: +91-9411656264
>
> --
>
>
>


 -- 
 With Best Wishes

 From:

 Naveen Shukla
 IIIT Allahabad
 B.Tech IT 4th year
 Mob No: 07860896972
 E-mail naveenshukla...@gmail.com 

>>>

--

Re: [algogeeks] Linked List question

2013-01-01 Thread Dave 
@Doom: Yes. It is necessary to go through the entire list. The code could 
look like this:
 
int* p = head;
int k = 1;
while( head )
{
head = head -> next;
k++;
if( k * (double)rand() < RAND_MAX )
p = head;
}
 
Dave

On Sunday, December 30, 2012 12:40:28 PM UTC-6, Doom wrote:

> Hi Dave
>
> Please help me with some additional clarification regarding the 
> implementation of this algo. How do we make use of random number generator?
>
> And is it necessary to traverse the list until the end? 
>
>
> On Friday, 28 December 2012 19:35:07 UTC+5:30, Dave wrote:
>>
>> @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
>> the kth node, set p to the kth node with probability 1/k. When you reach 
>> the end of the list, return p, which will point to a random node with 
>> uniform probability.
>>  
>> Dave
>>
>> On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
>>
>>> i mean the length of the linked list is not known to us.
>>> @udit how can we do this in single traversal ? i think we need to 
>>> traverse the linked list twice in your case.
>>> Please reply if i am wrong ?
>>>
>>> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal wrote:
>>>
 If the length of the linked is infinite then the above algo would do
 the needful.
 In case you have a finite length linked list, then you can normalize
 the random value using following:
 Suppose length of linked list is: l
 random number is: r; and r > l
 then new random number would be: r1 = r%l;
 now again use the above algo using new random number r1;

 On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
 > You said : "Given a linked list of infinite length"
 >
 > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
 >  wrote:
 >> But suppose a random number generate a value 5 and your linked list 
 has only
 >> four elements. In that case what would be the answer ???
 >>
 >>
 >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
 hpre...@gmail.com>
 >> wrote:
 >>>
 >>> Well my algo will be Something like this
 >>>
 >>> 1> Get a Random number. Perhaps You can have the function like 
 Randon(List
 >>> *head, int Randomnumber)
 >>>
 >>> 2> Use the function argument Randomnumber to loop the list.
 >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
 >>>head = head -> next;
 >>> }
 >>>
 >>> 3> print (head->value);
 >>>
 >>> 4> return ;
 >>>
 >>> Now as we are using byvalue when we return the value of head 
 remains the
 >>> same old head value. So everytime we call we are traversing the 
 same old
 >>> list.
 >>>
 >>>  The Random variable can be taken inside the function itself if the 
 user
 >>> is not taking the random value.
 >>>  i.e. int Randomnumber = random();  and now the user can calll 
 Simple
 >>> Random(head);
 >>>
 >>>
 >>>
 >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
 >>>  wrote:
 
  random node
 >>>
 >>>
 >>> --
 >>>
 >>>
 >>
 >>
 >>
 >>
 >> --
 >> With Best Wishes
 >>
 >> From:
 >>
 >> Naveen Shukla
 >> IIIT Allahabad
 >> B.Tech IT 4th year
 >> Mob No: 07860896972
 >> E-mail naveenshukla...@gmail.com
 >>
 >> --
 >>
 >>
 >
 > --
 >
 >



 --
 Udit Agarwal
 B.Tech. ( Information Technology ) , 7th Semester,
 Indian Institute of Information Technology
 Allahabad - 211012, India
 Email : udit...@gmail.com
 Mobile: +91-9411656264

 --



>>>
>>>
>>> -- 
>>> With Best Wishes
>>>
>>> From:
>>>
>>> Naveen Shukla
>>> IIIT Allahabad
>>> B.Tech IT 4th year
>>> Mob No: 07860896972
>>> E-mail naveenshukla...@gmail.com 
>>>
>>

--

Re: [algogeeks] Linked List question

2013-01-01 Thread Doom 
Hi Dave

Please help me with some additional clarification regarding the 
implementation of this algo. How do we make use of random number generator?

And is it necessary to traverse the list until the end? 


On Friday, 28 December 2012 19:35:07 UTC+5:30, Dave wrote:
>
> @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
> the kth node, set p to the kth node with probability 1/k. When you reach 
> the end of the list, return p, which will point to a random node with 
> uniform probability.
>  
> Dave
>
> On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
>
>> i mean the length of the linked list is not known to us.
>> @udit how can we do this in single traversal ? i think we need to 
>> traverse the linked list twice in your case.
>> Please reply if i am wrong ?
>>
>> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal  wrote:
>>
>>> If the length of the linked is infinite then the above algo would do
>>> the needful.
>>> In case you have a finite length linked list, then you can normalize
>>> the random value using following:
>>> Suppose length of linked list is: l
>>> random number is: r; and r > l
>>> then new random number would be: r1 = r%l;
>>> now again use the above algo using new random number r1;
>>>
>>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
>>> > You said : "Given a linked list of infinite length"
>>> >
>>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>>> >  wrote:
>>> >> But suppose a random number generate a value 5 and your linked list 
>>> has only
>>> >> four elements. In that case what would be the answer ???
>>> >>
>>> >>
>>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
>>> hpre...@gmail.com>
>>> >> wrote:
>>> >>>
>>> >>> Well my algo will be Something like this
>>> >>>
>>> >>> 1> Get a Random number. Perhaps You can have the function like 
>>> Randon(List
>>> >>> *head, int Randomnumber)
>>> >>>
>>> >>> 2> Use the function argument Randomnumber to loop the list.
>>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>> >>>head = head -> next;
>>> >>> }
>>> >>>
>>> >>> 3> print (head->value);
>>> >>>
>>> >>> 4> return ;
>>> >>>
>>> >>> Now as we are using byvalue when we return the value of head remains 
>>> the
>>> >>> same old head value. So everytime we call we are traversing the same 
>>> old
>>> >>> list.
>>> >>>
>>> >>>  The Random variable can be taken inside the function itself if the 
>>> user
>>> >>> is not taking the random value.
>>> >>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>>> >>> Random(head);
>>> >>>
>>> >>>
>>> >>>
>>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>>> >>>  wrote:
>>> 
>>>  random node
>>> >>>
>>> >>>
>>> >>> --
>>> >>>
>>> >>>
>>> >>
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> With Best Wishes
>>> >>
>>> >> From:
>>> >>
>>> >> Naveen Shukla
>>> >> IIIT Allahabad
>>> >> B.Tech IT 4th year
>>> >> Mob No: 07860896972
>>> >> E-mail naveenshukla...@gmail.com
>>> >>
>>> >> --
>>> >>
>>> >>
>>> >
>>> > --
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>> Udit Agarwal
>>> B.Tech. ( Information Technology ) , 7th Semester,
>>> Indian Institute of Information Technology
>>> Allahabad - 211012, India
>>> Email : udit...@gmail.com
>>> Mobile: +91-9411656264
>>>
>>> --
>>>
>>>
>>>
>>
>>
>> -- 
>> With Best Wishes
>>
>> From:
>>
>> Naveen Shukla
>> IIIT Allahabad
>> B.Tech IT 4th year
>> Mob No: 07860896972
>> E-mail naveenshukla...@gmail.com 
>>
>

--

Re: [algogeeks] Linked List question

2012-12-28 Thread Dave 
@Udit: Here is the proof: At step k, node k is selected with probability 
1/k. On the (k+1)st step, node k is replaced with probability 1/(k+1). Thus 
it is retained with probability 1 - 1/(k+1) = k/(k+1). On subsequent steps, 
node k is retained with probabilities (k+1)/(k+2), (k+2)/(k+3), ..., 
(n-1)/n. Thus, node k is selected on the kth step and then retained until 
the end of the list with probability 1/k * k/(k+1) * (k+1)/(k+2) * ... * 
(n-1) / n. Each denominator cancels with the succeeding numerator, so the 
product collapses to 1/n.
 
Dave

On Friday, December 28, 2012 10:46:17 AM UTC-6, Udit Agarwal wrote:

> @Dave: U said that the node p returned will be assigned to some kth 
> node with probability 1/k. then the probability for p to be assigned 
> to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is 
> the node p is assigned with uniform probability. 
>
> On Fri, Dec 28, 2012 at 7:35 PM, Dave > 
> wrote: 
> > @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
> the 
> > kth node, set p to the kth node with probability 1/k. When you reach the 
> end 
> > of the list, return p, which will point to a random node with uniform 
> > probability. 
> > 
> > Dave 
> > 
> > On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote: 
> >> 
> >> i mean the length of the linked list is not known to us. 
> >> @udit how can we do this in single traversal ? i think we need to 
> traverse 
> >> the linked list twice in your case. 
> >> Please reply if i am wrong ? 
> >> 
> >> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal  
> wrote: 
> >>> 
> >>> If the length of the linked is infinite then the above algo would do 
> >>> the needful. 
> >>> In case you have a finite length linked list, then you can normalize 
> >>> the random value using following: 
> >>> Suppose length of linked list is: l 
> >>> random number is: r; and r > l 
> >>> then new random number would be: r1 = r%l; 
> >>> now again use the above algo using new random number r1; 
> >>> 
> >>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote: 
> >>> > You said : "Given a linked list of infinite length" 
> >>> > 
> >>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla 
> >>> >  wrote: 
> >>> >> But suppose a random number generate a value 5 and your linked list 
> >>> >> has only 
> >>> >> four elements. In that case what would be the answer ??? 
> >>> >> 
> >>> >> 
> >>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
> >>> >>  
> >>> 
> >>> >> wrote: 
> >>> >>> 
> >>> >>> Well my algo will be Something like this 
> >>> >>> 
> >>> >>> 1> Get a Random number. Perhaps You can have the function like 
> >>> >>> Randon(List 
> >>> >>> *head, int Randomnumber) 
> >>> >>> 
> >>> >>> 2> Use the function argument Randomnumber to loop the list. 
> >>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){ 
> >>> >>>head = head -> next; 
> >>> >>> } 
> >>> >>> 
> >>> >>> 3> print (head->value); 
> >>> >>> 
> >>> >>> 4> return ; 
> >>> >>> 
> >>> >>> Now as we are using byvalue when we return the value of head 
> remains 
> >>> >>> the 
> >>> >>> same old head value. So everytime we call we are traversing the 
> same 
> >>> >>> old 
> >>> >>> list. 
> >>> >>> 
> >>> >>>  The Random variable can be taken inside the function itself if 
> the 
> >>> >>> user 
> >>> >>> is not taking the random value. 
> >>> >>>  i.e. int Randomnumber = random();  and now the user can calll 
> Simple 
> >>> >>> Random(head); 
> >>> >>> 
> >>> >>> 
> >>> >>> 
> >>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla 
> >>> >>>  wrote: 
> >>>  
> >>>  random node 
> >>> >>> 
> >>> >>> 
> >>> >>> -- 
> >>> >>> 
> >>> >>> 
> >>> >> 
> >>> >> 
> >>> >> 
> >>> >> 
> >>> >> -- 
> >>> >> With Best Wishes 
> >>> >> 
> >>> >> From: 
> >>> >> 
> >>> >> Naveen Shukla 
> >>> >> IIIT Allahabad 
> >>> >> B.Tech IT 4th year 
> >>> >> Mob No: 07860896972 
> >>> >> E-mail naveenshukla...@gmail.com 
> >>> >> 
> >>> >> -- 
> >>> >> 
> >>> >> 
> >>> > 
> >>> > -- 
> >>> > 
> >>> > 
> >>> 
> >>> 
> >>> 
> >>> -- 
> >>> Udit Agarwal 
> >>> B.Tech. ( Information Technology ) , 7th Semester, 
> >>> Indian Institute of Information Technology 
> >>> Allahabad - 211012, India 
> >>> Email : udit...@gmail.com 
> >>> Mobile: +91-9411656264 
> >>> 
> >>> -- 
> >>> 
> >>> 
> >> 
> >> 
> >> 
> >> -- 
> >> With Best Wishes 
> >> 
> >> From: 
> >> 
> >> Naveen Shukla 
> >> IIIT Allahabad 
> >> B.Tech IT 4th year 
> >> Mob No: 07860896972 
> >> E-mail naveenshukla...@gmail.com 
> > 
> > -- 
> > 
> > 
>
>
>
> -- 
> Udit Agarwal 
> B.Tech. ( Information Technology ) , 7th Semester, 
> Indian Institute of Information Technology 
> Allahabad - 211012, India 
> Email : udit...@gmail.com  
> Mobile: +91-9411656264 
>

--

Re: [algogeeks] Linked List question

2012-12-28 Thread Udit Agarwal 
@Dave: U said that the node p returned will be assigned to some kth
node with probability 1/k. then the probability for p to be assigned
to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is
the node p is assigned with uniform probability.

On Fri, Dec 28, 2012 at 7:35 PM, Dave  wrote:
> @Sanjeev: Set a pointer p to the first node. Traverse the list. When at the
> kth node, set p to the kth node with probability 1/k. When you reach the end
> of the list, return p, which will point to a random node with uniform
> probability.
>
> Dave
>
> On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
>>
>> i mean the length of the linked list is not known to us.
>> @udit how can we do this in single traversal ? i think we need to traverse
>> the linked list twice in your case.
>> Please reply if i am wrong ?
>>
>> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal  wrote:
>>>
>>> If the length of the linked is infinite then the above algo would do
>>> the needful.
>>> In case you have a finite length linked list, then you can normalize
>>> the random value using following:
>>> Suppose length of linked list is: l
>>> random number is: r; and r > l
>>> then new random number would be: r1 = r%l;
>>> now again use the above algo using new random number r1;
>>>
>>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
>>> > You said : "Given a linked list of infinite length"
>>> >
>>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>>> >  wrote:
>>> >> But suppose a random number generate a value 5 and your linked list
>>> >> has only
>>> >> four elements. In that case what would be the answer ???
>>> >>
>>> >>
>>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
>>> >> 
>>>
>>> >> wrote:
>>> >>>
>>> >>> Well my algo will be Something like this
>>> >>>
>>> >>> 1> Get a Random number. Perhaps You can have the function like
>>> >>> Randon(List
>>> >>> *head, int Randomnumber)
>>> >>>
>>> >>> 2> Use the function argument Randomnumber to loop the list.
>>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>> >>>head = head -> next;
>>> >>> }
>>> >>>
>>> >>> 3> print (head->value);
>>> >>>
>>> >>> 4> return ;
>>> >>>
>>> >>> Now as we are using byvalue when we return the value of head remains
>>> >>> the
>>> >>> same old head value. So everytime we call we are traversing the same
>>> >>> old
>>> >>> list.
>>> >>>
>>> >>>  The Random variable can be taken inside the function itself if the
>>> >>> user
>>> >>> is not taking the random value.
>>> >>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>>> >>> Random(head);
>>> >>>
>>> >>>
>>> >>>
>>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>>> >>>  wrote:
>>> 
>>>  random node
>>> >>>
>>> >>>
>>> >>> --
>>> >>>
>>> >>>
>>> >>
>>> >>
>>> >>
>>> >>
>>> >> --
>>> >> With Best Wishes
>>> >>
>>> >> From:
>>> >>
>>> >> Naveen Shukla
>>> >> IIIT Allahabad
>>> >> B.Tech IT 4th year
>>> >> Mob No: 07860896972
>>> >> E-mail naveenshukla...@gmail.com
>>> >>
>>> >> --
>>> >>
>>> >>
>>> >
>>> > --
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>> Udit Agarwal
>>> B.Tech. ( Information Technology ) , 7th Semester,
>>> Indian Institute of Information Technology
>>> Allahabad - 211012, India
>>> Email : udit...@gmail.com
>>> Mobile: +91-9411656264
>>>
>>> --
>>>
>>>
>>
>>
>>
>> --
>> With Best Wishes
>>
>> From:
>>
>> Naveen Shukla
>> IIIT Allahabad
>> B.Tech IT 4th year
>> Mob No: 07860896972
>> E-mail naveenshukla...@gmail.com
>
> --
>
>



-- 
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : uditii...@gmail.com
Mobile: +91-9411656264

--

Re: [algogeeks] Linked List question

2012-12-28 Thread Dave 
@Sanjeev: Set a pointer p to the first node. Traverse the list. When at the 
kth node, set p to the kth node with probability 1/k. When you reach the 
end of the list, return p, which will point to a random node with uniform 
probability.
 
Dave

On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:

> i mean the length of the linked list is not known to us.
> @udit how can we do this in single traversal ? i think we need to traverse 
> the linked list twice in your case.
> Please reply if i am wrong ?
>
> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal 
> > wrote:
>
>> If the length of the linked is infinite then the above algo would do
>> the needful.
>> In case you have a finite length linked list, then you can normalize
>> the random value using following:
>> Suppose length of linked list is: l
>> random number is: r; and r > l
>> then new random number would be: r1 = r%l;
>> now again use the above algo using new random number r1;
>>
>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth > 
>> wrote:
>> > You said : "Given a linked list of infinite length"
>> >
>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>> > > wrote:
>> >> But suppose a random number generate a value 5 and your linked list 
>> has only
>> >> four elements. In that case what would be the answer ???
>> >>
>> >>
>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
>> hpre...@gmail.com >
>> >> wrote:
>> >>>
>> >>> Well my algo will be Something like this
>> >>>
>> >>> 1> Get a Random number. Perhaps You can have the function like 
>> Randon(List
>> >>> *head, int Randomnumber)
>> >>>
>> >>> 2> Use the function argument Randomnumber to loop the list.
>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>> >>>head = head -> next;
>> >>> }
>> >>>
>> >>> 3> print (head->value);
>> >>>
>> >>> 4> return ;
>> >>>
>> >>> Now as we are using byvalue when we return the value of head remains 
>> the
>> >>> same old head value. So everytime we call we are traversing the same 
>> old
>> >>> list.
>> >>>
>> >>>  The Random variable can be taken inside the function itself if the 
>> user
>> >>> is not taking the random value.
>> >>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>> >>> Random(head);
>> >>>
>> >>>
>> >>>
>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>> >>> > wrote:
>> 
>>  random node
>> >>>
>> >>>
>> >>> --
>> >>>
>> >>>
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> With Best Wishes
>> >>
>> >> From:
>> >>
>> >> Naveen Shukla
>> >> IIIT Allahabad
>> >> B.Tech IT 4th year
>> >> Mob No: 07860896972
>> >> E-mail naveenshukla...@gmail.com 
>> >>
>> >> --
>> >>
>> >>
>> >
>> > --
>> >
>> >
>>
>>
>>
>> --
>> Udit Agarwal
>> B.Tech. ( Information Technology ) , 7th Semester,
>> Indian Institute of Information Technology
>> Allahabad - 211012, India
>> Email : udit...@gmail.com 
>> Mobile: +91-9411656264
>>
>> --
>>
>>
>>
>
>
> -- 
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshukla...@gmail.com  
>

--

Re: [algogeeks] Linked List question

2012-12-27 Thread naveen shukla 
thanks udit :) i think this approach will surely work.

On Fri, Dec 28, 2012 at 1:19 PM, Udit Agarwal  wrote:

> no.. i din't know that in ur case infinite number of nodes means
> unknown number of the finite nodes. I thought it to be like we have as
> much number of node as we want.
> and as u said if the length is know to be 4 and random number is 5
> then for that i gave my approach like u can now generate a new number
> as 5%4 = 1.
> For case u don't know the number of nodes in the linked list (which is
> finite), then we can use following approach:
> For each node in the linked list, generate a random number and as u
> traverse it keep track of the node address which is allotted minimum
> random number and then finally return that node's address as the ans.
> As each of the node is equally probable to be allotted the minimum
> random number so the final answer that we have will be completely
> random.
> Please reply in case u still have some doubt.
> Thanks
>
> On Fri, Dec 28, 2012 at 10:48 AM, naveen shukla
>  wrote:
> > i mean the length of the linked list is not known to us.
> > @udit how can we do this in single traversal ? i think we need to
> traverse
> > the linked list twice in your case.
> > Please reply if i am wrong ?
> >
> >
> > On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal 
> wrote:
> >>
> >> If the length of the linked is infinite then the above algo would do
> >> the needful.
> >> In case you have a finite length linked list, then you can normalize
> >> the random value using following:
> >> Suppose length of linked list is: l
> >> random number is: r; and r > l
> >> then new random number would be: r1 = r%l;
> >> now again use the above algo using new random number r1;
> >>
> >> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth 
> wrote:
> >> > You said : "Given a linked list of infinite length"
> >> >
> >> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
> >> >  wrote:
> >> >> But suppose a random number generate a value 5 and your linked list
> has
> >> >> only
> >> >> four elements. In that case what would be the answer ???
> >> >>
> >> >>
> >> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
> >> >> 
> >> >> wrote:
> >> >>>
> >> >>> Well my algo will be Something like this
> >> >>>
> >> >>> 1> Get a Random number. Perhaps You can have the function like
> >> >>> Randon(List
> >> >>> *head, int Randomnumber)
> >> >>>
> >> >>> 2> Use the function argument Randomnumber to loop the list.
> >> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
> >> >>>head = head -> next;
> >> >>> }
> >> >>>
> >> >>> 3> print (head->value);
> >> >>>
> >> >>> 4> return ;
> >> >>>
> >> >>> Now as we are using byvalue when we return the value of head remains
> >> >>> the
> >> >>> same old head value. So everytime we call we are traversing the same
> >> >>> old
> >> >>> list.
> >> >>>
> >> >>>  The Random variable can be taken inside the function itself if the
> >> >>> user
> >> >>> is not taking the random value.
> >> >>>  i.e. int Randomnumber = random();  and now the user can calll
> Simple
> >> >>> Random(head);
> >> >>>
> >> >>>
> >> >>>
> >> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
> >> >>>  wrote:
> >> 
> >>  random node
> >> >>>
> >> >>>
> >> >>> --
> >> >>>
> >> >>>
> >> >>
> >> >>
> >> >>
> >> >>
> >> >> --
> >> >> With Best Wishes
> >> >>
> >> >> From:
> >> >>
> >> >> Naveen Shukla
> >> >> IIIT Allahabad
> >> >> B.Tech IT 4th year
> >> >> Mob No: 07860896972
> >> >> E-mail naveenshuklasweetdrea...@gmail.com
> >> >>
> >> >> --
> >> >>
> >> >>
> >> >
> >> > --
> >> >
> >> >
> >>
> >>
> >>
> >> --
> >> Udit Agarwal
> >> B.Tech. ( Information Technology ) , 7th Semester,
> >> Indian Institute of Information Technology
> >> Allahabad - 211012, India
> >> Email : uditii...@gmail.com
> >> Mobile: +91-9411656264
> >>
> >> --
> >>
> >>
> >
> >
> >
> > --
> > With Best Wishes
> >
> > From:
> >
> > Naveen Shukla
> > IIIT Allahabad
> > B.Tech IT 4th year
> > Mob No: 07860896972
> > E-mail naveenshuklasweetdrea...@gmail.com
> >
> > --
> >
> >
>
>
>
> --
> Udit Agarwal
> B.Tech. ( Information Technology ) , 7th Semester,
> Indian Institute of Information Technology
> Allahabad - 211012, India
> Email : uditii...@gmail.com
> Mobile: +91-9411656264
>
> --
>
>
>


-- 
With Best Wishes

From:

Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshuklasweetdrea...@gmail.com

--

Re: [algogeeks] Linked List question

2012-12-27 Thread Udit Agarwal 
no.. i din't know that in ur case infinite number of nodes means
unknown number of the finite nodes. I thought it to be like we have as
much number of node as we want.
and as u said if the length is know to be 4 and random number is 5
then for that i gave my approach like u can now generate a new number
as 5%4 = 1.
For case u don't know the number of nodes in the linked list (which is
finite), then we can use following approach:
For each node in the linked list, generate a random number and as u
traverse it keep track of the node address which is allotted minimum
random number and then finally return that node's address as the ans.
As each of the node is equally probable to be allotted the minimum
random number so the final answer that we have will be completely
random.
Please reply in case u still have some doubt.
Thanks

On Fri, Dec 28, 2012 at 10:48 AM, naveen shukla
 wrote:
> i mean the length of the linked list is not known to us.
> @udit how can we do this in single traversal ? i think we need to traverse
> the linked list twice in your case.
> Please reply if i am wrong ?
>
>
> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal  wrote:
>>
>> If the length of the linked is infinite then the above algo would do
>> the needful.
>> In case you have a finite length linked list, then you can normalize
>> the random value using following:
>> Suppose length of linked list is: l
>> random number is: r; and r > l
>> then new random number would be: r1 = r%l;
>> now again use the above algo using new random number r1;
>>
>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
>> > You said : "Given a linked list of infinite length"
>> >
>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>> >  wrote:
>> >> But suppose a random number generate a value 5 and your linked list has
>> >> only
>> >> four elements. In that case what would be the answer ???
>> >>
>> >>
>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri
>> >> 
>> >> wrote:
>> >>>
>> >>> Well my algo will be Something like this
>> >>>
>> >>> 1> Get a Random number. Perhaps You can have the function like
>> >>> Randon(List
>> >>> *head, int Randomnumber)
>> >>>
>> >>> 2> Use the function argument Randomnumber to loop the list.
>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>> >>>head = head -> next;
>> >>> }
>> >>>
>> >>> 3> print (head->value);
>> >>>
>> >>> 4> return ;
>> >>>
>> >>> Now as we are using byvalue when we return the value of head remains
>> >>> the
>> >>> same old head value. So everytime we call we are traversing the same
>> >>> old
>> >>> list.
>> >>>
>> >>>  The Random variable can be taken inside the function itself if the
>> >>> user
>> >>> is not taking the random value.
>> >>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>> >>> Random(head);
>> >>>
>> >>>
>> >>>
>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>> >>>  wrote:
>> 
>>  random node
>> >>>
>> >>>
>> >>> --
>> >>>
>> >>>
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> With Best Wishes
>> >>
>> >> From:
>> >>
>> >> Naveen Shukla
>> >> IIIT Allahabad
>> >> B.Tech IT 4th year
>> >> Mob No: 07860896972
>> >> E-mail naveenshuklasweetdrea...@gmail.com
>> >>
>> >> --
>> >>
>> >>
>> >
>> > --
>> >
>> >
>>
>>
>>
>> --
>> Udit Agarwal
>> B.Tech. ( Information Technology ) , 7th Semester,
>> Indian Institute of Information Technology
>> Allahabad - 211012, India
>> Email : uditii...@gmail.com
>> Mobile: +91-9411656264
>>
>> --
>>
>>
>
>
>
> --
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshuklasweetdrea...@gmail.com
>
> --
>
>



-- 
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : uditii...@gmail.com
Mobile: +91-9411656264

--

Re: [algogeeks] Linked List question

2012-12-27 Thread naveen shukla 
i mean the length of the linked list is not known to us.
@udit how can we do this in single traversal ? i think we need to traverse
the linked list twice in your case.
Please reply if i am wrong ?

On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal  wrote:

> If the length of the linked is infinite then the above algo would do
> the needful.
> In case you have a finite length linked list, then you can normalize
> the random value using following:
> Suppose length of linked list is: l
> random number is: r; and r > l
> then new random number would be: r1 = r%l;
> now again use the above algo using new random number r1;
>
> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
> > You said : "Given a linked list of infinite length"
> >
> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
> >  wrote:
> >> But suppose a random number generate a value 5 and your linked list has
> only
> >> four elements. In that case what would be the answer ???
> >>
> >>
> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
> hprem...@gmail.com>
> >> wrote:
> >>>
> >>> Well my algo will be Something like this
> >>>
> >>> 1> Get a Random number. Perhaps You can have the function like
> Randon(List
> >>> *head, int Randomnumber)
> >>>
> >>> 2> Use the function argument Randomnumber to loop the list.
> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
> >>>head = head -> next;
> >>> }
> >>>
> >>> 3> print (head->value);
> >>>
> >>> 4> return ;
> >>>
> >>> Now as we are using byvalue when we return the value of head remains
> the
> >>> same old head value. So everytime we call we are traversing the same
> old
> >>> list.
> >>>
> >>>  The Random variable can be taken inside the function itself if the
> user
> >>> is not taking the random value.
> >>>  i.e. int Randomnumber = random();  and now the user can calll Simple
> >>> Random(head);
> >>>
> >>>
> >>>
> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
> >>>  wrote:
> 
>  random node
> >>>
> >>>
> >>> --
> >>>
> >>>
> >>
> >>
> >>
> >>
> >> --
> >> With Best Wishes
> >>
> >> From:
> >>
> >> Naveen Shukla
> >> IIIT Allahabad
> >> B.Tech IT 4th year
> >> Mob No: 07860896972
> >> E-mail naveenshuklasweetdrea...@gmail.com
> >>
> >> --
> >>
> >>
> >
> > --
> >
> >
>
>
>
> --
> Udit Agarwal
> B.Tech. ( Information Technology ) , 7th Semester,
> Indian Institute of Information Technology
> Allahabad - 211012, India
> Email : uditii...@gmail.com
> Mobile: +91-9411656264
>
> --
>
>
>


-- 
With Best Wishes

From:

Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshuklasweetdrea...@gmail.com

--

Re: [algogeeks] Linked List question

2012-12-27 Thread Udit Agarwal 
If the length of the linked is infinite then the above algo would do
the needful.
In case you have a finite length linked list, then you can normalize
the random value using following:
Suppose length of linked list is: l
random number is: r; and r > l
then new random number would be: r1 = r%l;
now again use the above algo using new random number r1;

On Thu, Dec 27, 2012 at 4:12 PM, Vineeth  wrote:
> You said : "Given a linked list of infinite length"
>
> On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>  wrote:
>> But suppose a random number generate a value 5 and your linked list has only
>> four elements. In that case what would be the answer ???
>>
>>
>> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
>> wrote:
>>>
>>> Well my algo will be Something like this
>>>
>>> 1> Get a Random number. Perhaps You can have the function like Randon(List
>>> *head, int Randomnumber)
>>>
>>> 2> Use the function argument Randomnumber to loop the list.
>>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>>head = head -> next;
>>> }
>>>
>>> 3> print (head->value);
>>>
>>> 4> return ;
>>>
>>> Now as we are using byvalue when we return the value of head remains the
>>> same old head value. So everytime we call we are traversing the same old
>>> list.
>>>
>>>  The Random variable can be taken inside the function itself if the user
>>> is not taking the random value.
>>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>>> Random(head);
>>>
>>>
>>>
>>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>>>  wrote:

 random node
>>>
>>>
>>> --
>>>
>>>
>>
>>
>>
>>
>> --
>> With Best Wishes
>>
>> From:
>>
>> Naveen Shukla
>> IIIT Allahabad
>> B.Tech IT 4th year
>> Mob No: 07860896972
>> E-mail naveenshuklasweetdrea...@gmail.com
>>
>> --
>>
>>
>
> --
>
>



-- 
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : uditii...@gmail.com
Mobile: +91-9411656264

--

Re: [algogeeks] Linked List question

2012-12-27 Thread Vineeth 
You said : "Given a linked list of infinite length"

On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
 wrote:
> But suppose a random number generate a value 5 and your linked list has only
> four elements. In that case what would be the answer ???
>
>
> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
> wrote:
>>
>> Well my algo will be Something like this
>>
>> 1> Get a Random number. Perhaps You can have the function like Randon(List
>> *head, int Randomnumber)
>>
>> 2> Use the function argument Randomnumber to loop the list.
>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>head = head -> next;
>> }
>>
>> 3> print (head->value);
>>
>> 4> return ;
>>
>> Now as we are using byvalue when we return the value of head remains the
>> same old head value. So everytime we call we are traversing the same old
>> list.
>>
>>  The Random variable can be taken inside the function itself if the user
>> is not taking the random value.
>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>> Random(head);
>>
>>
>>
>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>>  wrote:
>>>
>>> random node
>>
>>
>> --
>>
>>
>
>
>
>
> --
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshuklasweetdrea...@gmail.com
>
> --
>
>

--

Re: [algogeeks] Linked List question

2012-12-27 Thread Prem Krishna Chettri 
Those are the Cornor Test Cases.. Well we here talk about Algos and
Complexity (Atmost Pseudo code ) not about unit test cases and source
code.. :)

Ofcourse U can include those checks  either when U call the function or
inside the functions..

On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla <
naveenshuklasweetdrea...@gmail.com> wrote:

> But suppose a random number generate a value 5 and your linked list has
> only four elements. In that case what would be the answer ???
>
> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
> wrote:
>
>> Well my algo will be Something like this
>>
>> 1> Get a Random number. Perhaps You can have the function like
>> Randon(List *head, int Randomnumber)
>>
>> 2> Use the function argument Randomnumber to loop the list.
>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>>head = head -> next;
>> }
>>
>> 3> print (head->value);
>>
>> 4> return ;
>>
>> Now as we are using byvalue when we return the value of head remains the
>> same old head value. So everytime we call we are traversing the same old
>> list.
>>
>>  The Random variable can be taken inside the function itself if the user
>> is not taking the random value.
>>  i.e. int Randomnumber = random();  and now the user can calll Simple
>> Random(head);
>>
>>
>>
>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla <
>> naveenshuklasweetdrea...@gmail.com> wrote:
>>
>>> random node
>>
>>
>>  --
>>
>>
>>
>
>
>
> --
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshuklasweetdrea...@gmail.com
>
> --
>
>
>

--

Re: [algogeeks] Linked List question

2012-12-27 Thread naveen shukla 
But suppose a random number generate a value 5 and your linked list has
only four elements. In that case what would be the answer ???

On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri wrote:

> Well my algo will be Something like this
>
> 1> Get a Random number. Perhaps You can have the function like Randon(List
> *head, int Randomnumber)
>
> 2> Use the function argument Randomnumber to loop the list.
> i.e. for(int count=0;count<=Randomnumber;count++ ){
>head = head -> next;
> }
>
> 3> print (head->value);
>
> 4> return ;
>
> Now as we are using byvalue when we return the value of head remains the
> same old head value. So everytime we call we are traversing the same old
> list.
>
>  The Random variable can be taken inside the function itself if the user
> is not taking the random value.
>  i.e. int Randomnumber = random();  and now the user can calll Simple
> Random(head);
>
>
>
> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla <
> naveenshuklasweetdrea...@gmail.com> wrote:
>
>> random node
>
>
>  --
>
>
>



-- 
With Best Wishes

From:

Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshuklasweetdrea...@gmail.com

--

Re: [algogeeks] Linked List question

2012-12-27 Thread Prem Krishna Chettri 
Well my algo will be Something like this

1> Get a Random number. Perhaps You can have the function like Randon(List
*head, int Randomnumber)

2> Use the function argument Randomnumber to loop the list.
i.e. for(int count=0;count<=Randomnumber;count++ ){
   head = head -> next;
}

3> print (head->value);

4> return ;

Now as we are using byvalue when we return the value of head remains the
same old head value. So everytime we call we are traversing the same old
list.

 The Random variable can be taken inside the function itself if the user is
not taking the random value.
 i.e. int Randomnumber = random();  and now the user can calll Simple
Random(head);



On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla <
naveenshuklasweetdrea...@gmail.com> wrote:

> random node

--

Re: [algogeeks] LINKED LIST QUESTION

2012-06-04 Thread atul anand 
well converting single linked list to balanced BST...this would also work

On Mon, Jun 4, 2012 at 4:29 PM, Nishant Pandey  wrote:

> Hi ,
>
> I think the only possiblity is to make it doubly linked list and then
> consider next & prev as left and right child like tree and then perform
> search as we in tree , it would serve the purpose .
> let me know if iam wrong .
>
> On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:
>
>> can be done using skip lists
>>
>>
>> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh 
>> wrote:
>>
>>> This is possible only if Linked List is sorted then we can apply Merge
>>> Sort for Linked List which would be in place.
>>>
>>> Otherwise the time complexity would be O(n logn).
>>>
>>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>>
 Hi we need find a node in linked list in O(logn). You can change the
 list as u like.

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
 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,
>>> Jeevitesh Shekhar Singh.*
>>>
>>>
>>>  --
>>> 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.
>>
>
>
>
> --
> Cheers,
>
> Nishant Pandey |Specialist Tools Development  |  
> npan...@google.com |
> +91-9911258345
>
>
>  --
> 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] LINKED LIST QUESTION

2012-06-04 Thread Nishant Pandey 
Hi ,

I think the only possiblity is to make it doubly linked list and then
consider next & prev as left and right child like tree and then perform
search as we in tree , it would serve the purpose .
let me know if iam wrong .

On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:

> can be done using skip lists
>
>
> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:
>
>> This is possible only if Linked List is sorted then we can apply Merge
>> Sort for Linked List which would be in place.
>>
>> Otherwise the time complexity would be O(n logn).
>>
>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>
>>> Hi we need find a node in linked list in O(logn). You can change the
>>> list as u like.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>>> 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,
>> Jeevitesh Shekhar Singh.*
>>
>>
>>  --
>> 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.
>



-- 
Cheers,

Nishant Pandey |Specialist Tools Development  |
npan...@google.com |
+91-9911258345

-- 
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] LINKED LIST QUESTION

2012-06-04 Thread atul anand 
as question says you can change the list as u like...i guess skip list is
the answer.

On Mon, Jun 4, 2012 at 3:51 PM, SANDEEP CHUGH wrote:

> can be done using skip lists
>
>
> On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:
>
>> This is possible only if Linked List is sorted then we can apply Merge
>> Sort for Linked List which would be in place.
>>
>> Otherwise the time complexity would be O(n logn).
>>
>> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>>
>>> Hi we need find a node in linked list in O(logn). You can change the
>>> list as u like.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>>> 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,
>> Jeevitesh Shekhar Singh.*
>>
>>
>>  --
>> 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] LINKED LIST QUESTION

2012-06-04 Thread SANDEEP CHUGH 
can be done using skip lists


On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh wrote:

> This is possible only if Linked List is sorted then we can apply Merge
> Sort for Linked List which would be in place.
>
> Otherwise the time complexity would be O(n logn).
>
> On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:
>
>> Hi we need find a node in linked list in O(logn). You can change the list
>> as u like.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
>> 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,
> Jeevitesh Shekhar Singh.*
>
>
>  --
> 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] LINKED LIST QUESTION

2012-06-04 Thread Jeevitesh 
This is possible only if Linked List is sorted then we can apply Merge Sort
for Linked List which would be in place.

Otherwise the time complexity would be O(n logn).

On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:

> Hi we need find a node in linked list in O(logn). You can change the list
> as u like.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
> 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,
Jeevitesh Shekhar Singh.*

-- 
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] LINKED LIST QUESTION

2012-06-04 Thread Amol Sharma 
not possible i suppose..
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad








On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI  wrote:

> Hi we need find a node in linked list in O(logn). You can change the list
> as u like.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/vSoEXlaRTEIJ.
> 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.