Re: [algogeeks] Linked List question
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 udit...@gmail.comwrote:
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 vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@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
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
naveenshukla...@gmail.com 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
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 udit...@gmail.com 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 vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@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
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
naveenshukla...@gmail.com 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
@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 udit...@gmail.comwrote:
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 vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@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
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
naveenshukla...@gmail.com 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
@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 udit...@gmail.comjavascript:
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 vineet...@gmail.comjavascript:
wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@gmail.com javascript: 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 javascript:
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
naveenshukla...@gmail.com javascript: wrote:
random node
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com javascript:
--
--
--
Udit Agarwal
B.Tech. ( Information Technology ) , 7th Semester,
Indian Institute of Information Technology
Allahabad - 211012, India
Email : udit...@gmail.com javascript:
Mobile: +91-9411656264
--
--
With Best Wishes
From:
Naveen Shukla
IIIT Allahabad
B.Tech IT 4th year
Mob No: 07860896972
E-mail naveenshukla...@gmail.com javascript:
--
Re: [algogeeks] Linked List question
@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 dave_and_da...@juno.com 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 udit...@gmail.com 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 vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@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
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
naveenshukla...@gmail.com 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
@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 dave_an...@juno.com javascript:
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 udit...@gmail.com
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 vineet...@gmail.com wrote:
You said : Given a linked list of infinite length
On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
naveenshukla...@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
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
naveenshukla...@gmail.com 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 javascript:
Mobile: +91-9411656264
--
[algogeeks] Linked List question
Given a linked list of infinite length. Write a function to return a random node. Constraints: 1 You can traverse a singly linked list only once. 2 You can not use any extra space. Thanks in advance. --
Re: [algogeeks] Linked List question
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
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.comwrote:
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
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
hprem...@gmail.comwrote:
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
You said : Given a linked list of infinite length
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 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
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
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 vineeth.n...@gmail.com wrote:
You said : Given a linked list of infinite length
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 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
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
--
--
--
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
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 uditii...@gmail.com 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 vineeth.n...@gmail.com wrote:
You said : Given a linked list of infinite length
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
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
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
--
--
--
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
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
naveenshuklasweetdrea...@gmail.com 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 uditii...@gmail.com 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 vineeth.n...@gmail.com wrote:
You said : Given a linked list of infinite length
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
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
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
--
--
--
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
thanks udit :) i think this approach will surely work.
On Fri, Dec 28, 2012 at 1:19 PM, Udit Agarwal uditii...@gmail.com 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
naveenshuklasweetdrea...@gmail.com 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 uditii...@gmail.com
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 vineeth.n...@gmail.com
wrote:
You said : Given a linked list of infinite length
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
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
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
--
--
--
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
--
[algogeeks] LINKED LIST QUESTION
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.
Re: [algogeeks] LINKED LIST QUESTION
not possible i suppose.. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI viharri@gmail.com 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.
Re: [algogeeks] LINKED LIST QUESTION
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 viharri@gmail.com 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
can be done using skip lists On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh jeeviteshshekha...@gmail.comwrote: 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 viharri@gmail.com 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
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 sandeep.aa...@gmail.comwrote: can be done using skip lists On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh jeeviteshshekha...@gmail.comwrote: 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 viharri@gmail.com 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
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 sandeep.aa...@gmail.comwrote: can be done using skip lists On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh jeeviteshshekha...@gmail.comwrote: 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 viharri@gmail.com 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.comgvib...@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
well converting single linked list to balanced BST...this would also work On Mon, Jun 4, 2012 at 4:29 PM, Nishant Pandey nishant.bits.me...@gmail.com 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 sandeep.aa...@gmail.comwrote: can be done using skip lists On Mon, Jun 4, 2012 at 3:03 PM, Jeevitesh jeeviteshshekha...@gmail.comwrote: 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 viharri@gmail.com 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.comgvib...@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.
