## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

would this be the same as selecting "k" elements via reservoir sampling and then generating another random number "j" between 1 and k and selecting the jth element from the reservoir?

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Classic example of resevior sampling problem :
Algorithm (for sampling first K elements, here K = 1):

1. For i = 1 to K:
R[i] = S[i]

2. For i = K + 1 to S.length:
j = random(0, i)
if(j <= k){
R[j] = S[i];

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public final int BAD_INPUT = Integer.MAX_VALUE;

Random rand = new Random();
int counter = 1;

int newRandVal = rand.nextInt(counter++);

if (newRandVal == 1)

}

return randomValueToReturn;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

reservoir sampling..here the value of k is 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Add a new node at the end of the linkedlist, while traversing count the number of nodes and make use of that count with equal probability.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Reservoir Sampling problem in Column 12 Problem 10 of book ' Programming Pearls'.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.