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 number
as 5%4 = 1.
For case u don't know the number of nodes in the linked list (which is
finite), then we can use following approach:
For each node in the linked list, generate a random number and as u
traverse it keep track of the node address which is allotted minimum
random number and then finally return that node's address as the ans.
As each of the node is equally probable to be allotted the minimum
random number so the final answer that we have will be completely
random.
Please reply in case u still have some doubt.
Thanks
On Fri, Dec 28, 2012 at 10:48 AM, naveen shukla
<naveenshuklasweetdrea...@gmail.com> 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 <uditii...@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 <vineeth.n...@gmail.com> wrote:
>> > 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, 2012 at 4:03 PM, Prem Krishna Chettri
>> >> <hprem...@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
>> >>> <naveenshuklasweetdrea...@gmail.com> wrote:
>> >>>>
>> >>>> random node
>> >>>
>> >>>
>> >>> --
>> >>>
>> >>>
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> With Best Wishes
>> >>
>> >> From:
>> >>
>> >> Naveen Shukla
>> >> IIIT Allahabad
>> >> B.Tech IT 4th year
>> >> Mob No: 07860896972
>> >> E-mail naveenshuklasweetdrea...@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
>>
>> --
>>
>>
>
>
>
> --
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshuklasweetdrea...@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
--
