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