Amazon Interview Question
Software Engineer / DevelopersCountry: 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