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)

- Ankur December 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankur December 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankur December 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sandipan December 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codeKiller December 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 "

- miki December 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- miki December 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankur December 16, 2011 | Flag
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.

- nitin December 14, 2011 | Flag Reply
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

- Anonymous December 15, 2011 | Flag Reply
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

- Laxmi Narsimha Rao Oruganti December 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Laxmi

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

- Anonymous December 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi guys I have already posted the solution.
Any comments.

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.

- nitin December 17, 2011 | Flag Reply
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

- getjar.com/todotasklist my android app December 18, 2011 | Flag Reply
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

- Coder December 19, 2011 | Flag Reply
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++) {
integers.add(sum[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;
}

- nmc January 02, 2012 | Flag Reply
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();
}
}

- Ketav January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

what is example for a corrupted sum.

- Doctor.Sai December 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- quark December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sonu.hzb.bhr December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sonu

Could you please explain your approach for the given example

- Anonymous December 15, 2011 | Flag
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?

- veeru December 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gaurav.gau December 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nascent Coder December 15, 2011 | 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