Author |
Topic: Random node from a singly linked list (Read 2768 times) |
|
neo_only
Newbie
Posts: 1
|
 |
Random node from a singly linked list
« on: Oct 18th, 2007, 12:45pm » |
 Quote  Modify
|
Hi,
This was a question asked in an interview. You are given a singly linked list, whose length is not known. We have to randomly pick a node from the list, such that the random function doesnt use the length of the list but also picks the node with a uniform distribution.
Traversing the list once and then using length to find the random node, makes two passes which should not happen. (He wants it in a single pass).
(He gave a hint that when only one node is there, we can say the probability of picking the node is one. If not, there is a 1/2 probability that is associated assuming there are only 2 nodes. He also said he can save the node values as he passes and make a decision but need not traverse all the n nodes...) I couldnt find the solution 
Thanks.
Neo
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Random node from a singly linked list
« Reply #1 on: Oct 18th, 2007, 1:20pm » |
Quote Modify
|
I am sure there is a thread on this.
Scan the list, take element k with probability 1/k. (if not, keep whatever element you have taken earlier).
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
 
Gender:
Posts: 55
|
|
Re: Random node from a singly linked list
« Reply #2 on: Oct 24th, 2007, 10:57am » |
Quote Modify
|
Take the first node and store it in the temporary storage.
Go to second node, now randomly chose one among the second node and the node stored in temporary location and replace the chosen node into the temporary storage. That's probability of 1/2.
Now move to the third node and repeat the same process and so on for the whole list.
At the end of the traversal, what you have in the temporary storage is a random node.
|
|
IP Logged |
www.gowrikumar.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print