Amazon Interview Question
SDE-2sCountry: India
Interview Type: Phone Interview
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.
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.
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
Simple solution check: Sum of elements should be 10 as there are 10 elements and each should be accounted for.
- Anonymous April 26, 20146210001000