## Amazon Interview Question for Software Engineer / Developers

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

can you please elaborate further. List is a linked list or just a pool of numbers.

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

It is a singly linked list. You have to return the random element. One solution is to make a scan to get the size of list and generate a random number b/w 0 to size. But this needs two scans of list. Try to make a single scan and still have the probability of selecting any node as same.

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

Search for Reservoir sampling

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

Example: N1->N2->N3->N4

Iterate through list from beginning
- Start by choosing between N1 and N2 with a 1/2 chance of picking either one.
- Then pick between ResultOf(N1,N2) and N3 with a 1/3 chance of picking N3 and 2/3 chance of picking ResultOf(N1,N2)
- Then pick between ResultOf(N1,N2,N3) and N4 with a 1/4 chance of picking N4 and 3/4 chance of picking ResultOf(N1,N2,N3)

Solution:
- Keep choosing between previousChoice and NewChoice with a 1/N chance of picking NewChoice and (N-1)/N chance of picking previousChoice where N is the Node number

Proof: If you go thorough the above example, N1 was chosen with a chance of (3/4)(2/3)(1/2)=(1/4)

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

I guess this will return a re-ordered list

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

@metical:
True.
Essentially reservoir sampling where size of reservoir = 1.

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

``````#include<stdio.h>
int main()
{
int r=0,n=0,sum=0;
scanf("%d",&n);
while(n)
{
r=n%10;
sum=sum+r;
if(sum>9)
sum=sum-9;
n=n/10;
}
printf("%d",sum);
return 0;
}``````

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

If we know the length of the list and can access any element at will, then just take list[rand(length)].

If we know the length of the list but cannot access every element at will (e.g. linked list?, or stream), then produce k=rand[length] and traverse the list until you get to the k-th element.

If we don't know the length of the list and cannot access its elements at will, then create a variable X, write the first element of the list to X, swap with the second element with probability 1/2, swap with the third element with probability 1/3, and so on. At the end, return X. One can prove by induction that this returns a uniformly random element from the list.

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

Credit due to some other dude who posted on CareerCup regarding a problem similar to this one.

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.