## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

what if the linked list is infinite ?

Here is an idea.

First randomly choose one of the first 2 element with same probabilities.

Then move to the third element , either choose the third element with probability of 1/3 or choose the chosen element of first step with probability of 2/3.

Keeping moving on. We always have an element chosen in our hand. whenever we need an element(means we assume the list is ended here) , print it.

```
public final int BAD_INPUT = Integer.MAX_VALUE;
public int getRandomlySampledNumber(Node head) {
if (head == null) return BAD_INPUT;
Random rand = new Random();
int randomValueToReturn = head.val;
int counter = 1;
while (head != null) {
int newRandVal = rand.nextInt(counter++);
if (newRandVal == 1)
randomValueToReturn = head.val;
head = head.next;
}
return randomValueToReturn;
}
```

Done using reservoir sampling

-Consider a linked list whose length is not known.

-for 1st node, probability is 100%, for second 50% and so on..

-doing this n times would give an equal probability for each node.

Here is my code:

```
public int findrandom()
{
Node curr=start;
int count=1, result=0, probability;
Random rand=new Random();
while(curr!=null)
{
probability=rand.nextInt(count)+1;
if(count==probability)
result=curr.info;
count++;
curr=curr.next;
}
return result;
}
```

Select each node with probability 1/k, where k is the node number, first starting from 1. Lookup reservoir sampling for explanation.

- Viatcheslav Gachkaylo January 18, 2013