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
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
@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,
@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,
@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
@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), ...,
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.
--
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 =
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
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
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,
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
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
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
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
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
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,
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
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,
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
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
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
22 matches
Mail list logo
