Linked list and probability

Note : Those who saw a flawed solution to “Puzzle : Noodles“, the post has been updated and now contains the correct solution.

This post is about a problem I solved more than 2 year back. Actually, it is a simple problem which was asked to my friend vaibhav gutpa during a technical interview conducted by amazon.

Problem : You are given a singly linked list and the length of the list is not known to you. Write a function which returns an element from the linked list uniformly randomly. You are allowed to traverse the linked list only once.

Solution : Had we been allowed to traverse the list twice, the job would have been easier, as we could just calculate the length n and then select an element with probability 1/n.

As we do not know the length of the list, we can maintain an invariant that the probability of selection of any element seen so far should be inversely proportional to the list traversed so far.

For example, we can initially compare the first two elements and select one element as a winner with probability 1/2. Now we make this winner contend with the third element. Of course, the winner should be given a bit more weightage as it has strugged to come so far. So the winner will be selected with probability 2/3 and the 3rd element with probability 1/3. Had the length of the list been only 3, you can see that winner is selected with probability (1/2)(2/3) = 1/3 or the third element is selected with probability 1/3. Similarly if there is a fourth element, we can choose the winner so far with probability 3/4 and the fourth element with 1/4.

This way we can traverse the entire list once. At the end, winner is guaranteed to have probability of selection as (1/n) if n is the length of the list.

–Saurabh Joshi


Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: