Amazon Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview




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

Simple solution check: Sum of elements should be 10 as there are 10 elements and each should be accounted for.

6210001000

- Anonymous April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is important to understand the thinking behind this solution. This is how I thought we can build a solution:-

Now let us start with a[0] = k and make k as high as possible.
This would mean a[k] >= 1
This would also mean there is atleast 1 i1 such that a[i1] = k

Now if a[k] = 1 it would imply a[1] >= 2 let us say j. So a[1] = j and j >= 2
So now a[j] >= 1. Again we have a i2 such that a[i2] = j.

And also we have another condition that the sum is equal to 10.
So, k + 1(from i1) +1(from i2) + j <= 10
k + 1 + 1 + 2<= 10
k <= 6

If k =6, then a[6] >= 1.
If a[6] = 1, then we have a[1] >= 2
If a[1] = 2, we have a[2] >= 1
If a[2] = 1, then we have a valid solution.

- prd April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

a[0]=n-4;a[1]=2;a[2]=1;a[n-4]=1; rest of all are zero's for any size n.

- sarat April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the logic like to reach this conclusion?

- linusyang2016 May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the logic is simple: due to induction we know 4 non-zero elements:
a[0] = k,
a[k] = 1,
a[1] = 2 (want to write 1, but cannot, 'cause we already have one 1, so we write 1+1),
a[2] = 1.

So, the rest n-4 elements are the 0 elements.
But we see that in first line of our induction analysis we have a[0] = k, and we already know that 0 presents n-4 times.
So, k = n-4.
So, we can substitute:
a[0] = n-4,
a[n-4] = 1,
a[1] = 2,
a[2] = 1.

- zr.roman December 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

a[0] = 9, all other elements are zeros. : 9, 0, 0, ........0

- Anonymous April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but what about a[9]=0, does this not violate the condition?

- Anonymous April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[0] = 8, a[8]=1, all the rest of the array elements are 0.

- Anonymous April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

then a[1] = 0 but there is a conflict with a[8] = 1

- Anonymous April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[0]=10, all the others are zeros.

- Anonymous April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In this case 0 should be repeated 10 times. Please note, size of an array is 10. In your case its 11.

- Anonymous April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[0]=6;a[1]=2;a[2]=1;a[6]=1; rest zero

- Anonymous April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n =number of elements eg=b[]=(2,1,3,0) op=a[]=(2,0,0,1,1,3,2,2,2,0)

Static K;
for(i=0;i<n;i++){
a[i+k]=b[i];
for(j=1;j<b[i];j++){
a[j+i+k]=i;
k++
}
}

comp =o(n2)

- lalit April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int givenNo = 3;  // y 
		int givenIdx = 5; // x
		int[] arr = new int[10];
		
		arr[givenIdx - 1] = givenNo; // problem defined a[x] = y 
		
		for(int i = 0;i<arr.length ; i ++){
			if(i != (givenIdx -1 )&& i<=givenNo){
				arr[i] = givenIdx;
			}
			
		}

- Abhijeet Pawar April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the second half of counting sort :)

- Anonymous July 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The solution should be as below.
If given array A has size n
we can start with A[0] = n-1,
then 0 will repeat itself (n-1) times.
Therefore, for n = 10
A[0] = 10-1 = 9
A[1] = 0
A[2] = 0
A[3] = 0
A[4] = 0
A[5] = 0
A[6] = 0
A[7] = 0
A[8] = 0
A[9] = 0

- Piyush April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in this case, I think, A[9] should be 1 because 9 has appeared once. I would think this answer is not what the interviewer is looking for.

- linusyang2016 May 11, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More