Get a random element in single direction linked list by one time traverse

Question

I have a single direction linked list without knowing its size.

I want to get a random element in this list, and I just have one time chance to traverse the list. (I am not allowed to traverse twice or more)

What’s the algorithm for this problem? Thanks!

Answer 1

This is just reservoir sampling with a reservoir of size 1.

Essentially it is really simple

1. Pick the first element regardless (for a list of length 1, the first element is always the sample).
2. For every other element with probability 1/n where n is the number of elements observed so far, you replace the already picked element with the current element you are on.

This is uniformly sampled, since the probability of picking any element at the end of the day is 1/n (exercise to the reader).

Answer 2

This is probably an interview question.Reservoir sampling is used by data scientist to store relevant data in limited storage from large stream of data.

If you have to collect k elements from any array with elements n, such that you probability of each element collected should be same (k/n), you follow two steps,

1) Store first k elements in the storage. 2) When the next element(k+1) comes from the stream obviously you have no space in your collection anymore.Generate a random number from o to n, if the generated random number is less than k suppose l, replace storage[l] with the (k+1) element from stream.

Now, coming back to your question, here storage size is 1.So you will pick the first node,iterate over the list for second element.Now generate the random number ,if its 1, leave the sample alone otherwise switch the storage element from list