## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

Linear Time Algo for this question can be as follows

First of all the user posted the wrong array .

The correct array should be

4, 5, 10, 7, 12, 13
a+b a+c a+d b+c b+d c+d

Now first calculate a+b+c+d which will be (sumofarray)/N-1

So here a+b+c+d = 17

Now take a[1] is a+c
and a[N-1] = b+c
subtracting them gives b-a = 2
a[0] is b+a=4
that gives b=3,a=1
Now u have a and b calculate c as a[1]-a=4
and d as9 . For this we traverse from a[1] to a[N-2]
We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array)

This will work in Linear Time

Now lets take an example with 8 elements to
let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8

then N=8 and array is
3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15
Now by above logic first
a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36
Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5
a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1
Now we have a=1,b=2
So we traverse from a[1] to a[N-2] to calculate values c to h
c= a[1]-a=4-1=3
d=a[2]-a=5-1=4
e=a[3]-a=6-1=5
similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8

This will work in O(n)

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

we dont need to calculate sum of the numbers here ..so algo will be O(N) where N is no of input nos.

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

I missed the term "non-decreasing" so we will have to sort the array first..complexity wud be nlogn :)

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

If you sort it then the a[7] would not be 5 !!!
So this will not work I think !

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

How you calculate number of out put because you use it generate one equation.

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

Ankur , when u say ::
"The correct array should be
4, 5, 10, 7, 12, 13"

Why do you think this should be the array when the question reads as ::
"pairwise sums of 'n' numbers are given in non-decreasing order "

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

Because its non-decreasing array its totally different problem, we dont know which is a+c and which is b+c.

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

Yeah I missed the non-decreasing part thing. But also its given in question that . "The input is: pairwise sums in sorted order" . So if we sort the input then we get the order of elements

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

There can be cases:
By looking at total numbers we can find the value of n as nC2=Total size of given array

Now ,

1 number is sum of first two minimum:
a1+a2=x1;
second number is first minimum and third minimum

that is
a1+a3

now third number can be
a1+a4 or a2+a3

if it a2+a3 than we got three equations with three variables and we can solve to get values of a1,a2,a3 and can substitute value in subsequent equation to verify. If all the elements of array verified than this is the right solution.
If any point of time condition is violated than this is not the right solution and we need to find another one.

Now next possibility can be
We can substitute a3 in terms of a2 by first two equations as a3=a2+x2-x1;

Now we can get third equation as
a1+a4=x3;

Again we can substitute a4 in terms of a2.

Now next we got two possibilities:
a1+a5=x4 or a2+a3=x4
and as if we use a2+a3=x4 we again can get the solution and than can try to substitute this solution in subsequent equations to verify.

Other again break a5 in term of a2 and again explore other two possibilities.

So the approach is the point where our minimum element in array can not give our next sum than at that point we are in actually the position of solving the whole set of equations formed till far.

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

We are given (as input) count of numbers 'n' and pairwise sums in sorted order.

Part-1:
If there are 'n' numbers, each number participates in 'n-1' pairs. If we get the sum of all pairwise sums, then the resultant value is (n-1) times the sum of numbers.

Take an example:
n = 4, a[1], a[2], a[3], a[4]
Pairwise Sums: a[1]+a[2], a[1]+a[3], a[1]+a[4], a[2]+a[3], a[2]+a[4], a[3]+a[4]
Sum(Numbers) = a[1] + a[2] + a[3] + a[4]
Sum(Pairwise Sums) = (a[1]+a[2]) + (a[1]+a[3]) + (a[1]+a[4]) + (a[2]+a[3]) + (a[2]+a[4]) + (a[3]+a[4]) = 3 (a[1]+a[2]+a[3]+a[4]) = (n-1) * Sum(Numbers)

We can find sum of numbers using the above equation.

Part-2:
Assume: First Lowest Number is given (i.e. b[1])
Number Of Pairs(n) = (n-1) + (n-2) + ... + 1 = (n-1)*n/2
Let us name the sorted order of pairs as, p[1], p[2], ..., p[(n-1)*n/2]
Let us call the resulting numbers in sorted order as b[1], b[2], ..., b[n]

p[1] is always b[1] + b[2]
b[2] = p[1] - b[1] = b[1] + b[2] - b[1] = b[2]

p[2] is always b[1] + b[3]
b[3] = p[2] - First Lowest Number = b[1] + b[3] - b[1] = b[3]

p[3] = min (b[1] + b[4], b[2] + b[3])
- We know b[1], b[2], b[3] by now
- Case: p[3] < b[2] + b[3]
-- Then it is p[3] is b[1] + b[4].
-- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
- Case: p[3] == b[2] + b[3]
-- If p[3] == p[4], then it means b[1] + b[4] == b[2] + b[3]
--- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
-- If p[3] != p[4], then it means p[4] = b[1] + b[4]
--- b[4] = p[4] - b[1] = b[1] + b[4] - b[1] = b[4]

p[4] = min(b[1] + b[5], b[2] + b[3])
- We know b[1], b[2], b[3], b[4] by now and repeat the logic

Thanks,
Laxmi

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

We are given (as input) count of numbers 'n' and pairwise sums in sorted order.

``Extra assumption: First Lowest Number is also given``

Number Of Pairs(n) = (n-1) + (n-2) + ... + 1 = (n-1)*n/2
Let us name the sorted order of pairs as, p[1], p[2], ..., p[(n-1)*n/2]
Let us call the resulting numbers in sorted order as b[1], b[2], ..., b[n]

p[1] is always b[1] + b[2]
- b[1] is known (assumption is that it is given)
- b[2] = p[1] - b[1] = b[1] + b[2] - b[1] = b[2]

p[2] is always b[1] + b[3]
- b[3] = p[2] - First Lowest Number = b[1] + b[3] - b[1] = b[3]

p[3] = min (b[1] + b[4], b[2] + b[3])
- We know b[1], b[2], b[3] by now
- Case: p[3] < b[2] + b[3]
-- Then p[3] is b[1] + b[4]
-- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
- Case: p[3] == b[2] + b[3]
-- If p[3] == p[4], then it means b[1] + b[4] == b[2] + b[3]
--- b[4] = p[3] - b[1] = b[1] + b[4] - b[1] = b[4]
-- If p[3] != p[4], then it means p[4] = b[1] + b[4]
--- b[4] = p[4] - b[1] = b[1] + b[4] - b[1] = b[4]

p[4] = min(b[1] + b[5], b[2] + b[4], max(b[1] + b[4], b[2] + b[3]) )
- We know b[1], b[2], b[3], b[4] by now and repeat the logic

Thanks,
Laxmi

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

@Laxmi

As you mentioned, your approach works only if b[1] is known. What if b[1] is not known

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

Hi guys I have already posted the solution.

By looking at total numbers we can find the value of n as nC2=Total size of given array

Now ,

1 number is sum of first two minimum:
a1+a2=x1;
second number is first minimum and third minimum

that is
a1+a3

now third number can be
a1+a4 or a2+a3

if it a2+a3 than we got three equations with three variables and we can solve to get values of a1,a2,a3 and can substitute value in subsequent equation to verify. If all the elements of array verified than this is the right solution.
If any point of time condition is violated than this is not the right solution and we need to find another one.

Now next possibility can be
We can substitute a3 in terms of a2 by first two equations as a3=a2+x2-x1;

Now we can get third equation as
a1+a4=x3;

Again we can substitute a4 in terms of a2.

Now next we got two possibilities:
a1+a5=x4 or a2+a3=x4
and as if we use a2+a3=x4 we again can get the solution and than can try to substitute this solution in subsequent equations to verify.

Other again break a5 in term of a2 and again explore other two possibilities.

So the approach is, the point where our minimum element in array can not give our next sum than at that point (as next element of sum array should be formed by a2_aa3)we are in actually the position of solving the whole set of equations formed till far.

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

array given in the question is wrong
correct one is
4 5 10 7 12 13
o/p:
1 3 4 9

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

We have

a+b,a+c,a+d,b+c,b+d,c+d
So we know out of n(n=4) elements, n-1 entries contain the smallest element in this case a. nth entry is the sum of 2nd largest+3rd largest. (b+c).

So we can add a+b + a+c - (b+c) to get 2a from which we can get a.
We subtract a from the first n-1 terms to get b,c,d

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

static int[] findNumbersFromPairwiseSum(int N,int sum[]){

int initial = sum[0];
int n[]=new int[N];
val:
for(int i =1;i<initial/2;i++){

n[0] = i;
List<Integer> integers = new ArrayList<Integer>();

for (int k = 0; k < sum.length; k++) {
}

for (int j = 1 ; j < N; j++) {
n[j] = integers.get(0)-n[0];
integers.remove(0);
int k = j-1;
while(k>=1){
if(integers.contains(new Integer((n[j]+n[k])))){
integers.remove(new Integer((n[j]+n[k])));
}else
continue val;
k--;
}

if(j == N-1) return n;

}

}
return null;
}

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

public class Terms {
private int pairSums[];
private int totalTerms;
private int t[];

public Terms(int a[],int b){
pairSums = new int[a.length];
totalTerms=b;
t = new int[b];
for(int i=0;i<a.length;i++)
pairSums[i] = a[i];
}

public int findTerm(){
int pair1 = pairSums[0];
int pair2 = pairSums[1];

/* find second and third term sumPair */
int index=1*(totalTerms-1)+1;
System.out.println(index);
int pairSum1 = pair1+pair2;
int a2 = pairSum1 - pairSums[index-1];
t[0] = a2/2;
System.out.print(t[0]+" ");

for(int i=1;i<totalTerms;i++){
t[i] = pairSums[i-1]-t[0];
System.out.print(t[i]+" ");
}
return 1;
}

/**
* @param args
*/
public static void main(String[] args) {
int a[] = {4,5,10,7,12,13};
Terms t1 = new Terms(a,4);
t1.findTerm();
}
}

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

what is example for a corrupted sum.

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

One insight could be:
[Sum of the pair-wise-sum / (n-1)] is not a whole number.
like in this case- (4+5+7+10+12+13)/(4-1) = 17 It is!

It's a necessary condition, but is allso sufficient? hmm..

so, it reduces to: can we split 17 into sum of 4 whole numbers! just to check the validity of Input.

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

you can calculate the number of numbers by this rule:
let n = number of sets.
and m = number of numbers

then m = (1 + (1+8n)^(1/2)) / 2;
if m is not a proper number then sth is wrong.

once you get the value of m then
(m-1)*(x1 + x2 + x3...+x(m)) = sum of all sets..

by this you can get x1+x2+x3+ .... + x(m)
now
get the sum (m-1)x1 + x2+ x3 + x4.....+ x(m) by adding the first (m-1) sets
once you have received this you can subtract the value of x1 + x2 + ....x(m) obtained from above and get the required value of x1.
after than you can get all the values of x's.

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

@sonu

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

guys, i didn't even get the question. can anyone please elaborate?

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

Hi Veeru, I am explaining question and answer as well.

i/p:
4 : count of numbers
4 5 7 10 12 13 : Pairwise sum

o/p: 1 3 4 9 : 4 numbers whose pair wise sum was given
4 == 1+3 (Pair wise sum of 1 and 3 is equal to 4 )
5 == 1+4
7 == 3+4
10 == 1+9
12 == 3+9
13 == 4+9
-----------
71== 3 *(1 + 3 + 4 + 9)
(Sum of the pairwise sum of n whole numbers) = nC2 * (Sum of n whole numbers)

With this we can find (Sum of n whole numbers).
and also we can find all n whole numbers.

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

Can u elaborate further how can we find all n whole numbers, from ur approach?

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.