@Ankur: The linked list is isomorphic to the non-negative integers, so selecting a random integer is equivalent to selecting a random node. There is no uniform distribution on the integers, so we can't find a uniform distribution on the nodes. One way to find a non-uniform distribution is by taking the n-th node of the list, where n = int(- log(random())), where random() generates uniform (0,1) random numbers. I presume that there are many more ways to do this.
Dave On Dec 23, 1:54 pm, Ankur Garg <[email protected]> wrote: > Suggest an algo with which u can find a random node in an infinitely long > linked list -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
