Amazon Interview Question
Software Engineer / DevelopersCountry: United States
we dont need to calculate sum of the numbers here ..so algo will be O(N) where N is no of input nos.
I missed the term "non-decreasing" so we will have to sort the array first..complexity wud be nlogn :)
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 "
Because its non-decreasing array its totally different problem, we dont know which is a+c and which is b+c.
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.
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
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
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.
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
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;
}
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();
}
}
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.
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.
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.
Linear Time Algo for this question can be as follows
- Ankur December 15, 2011First 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)