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