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 i

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, 20

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

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), ..., (

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 wro

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, Sa

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

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 n

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 wrote: > If the length of the linked is infinite the

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

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

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

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 wrote: > Well my algo will be Something like this > > 1> Get a Random number. Perhaps You can have the functi

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

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

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 wrote: > can be done usi

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

Re: [algogeeks] LINKED LIST QUESTION

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

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 wrote: > Hi we need find a node in linked list in O(logn). You can change the list > as

Re: [algogeeks] LINKED LIST QUESTION

not possible i suppose.. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Mon, Jun 4, 2012 at 3:00 PM