Amazon Interview Question SDE1s
Country: India
Interview Type: Written Test
I did the algebra for these summations got this result:
((m-1)*((n*l) - ((l*m)/2) - (2 * l) - ((3/2)*n) - ((1/4)*m) - 3 - ((n**2)/2) + (((2*(m**2)) - m)/6)))
However, this does not produce the same results as the code, unfortunately. For instance, m=2; n=4; l=6 produces -8 instead of the desired 14
Maybe I made a mistake? I think the algebra is quite sound. I think the equation is wrong somehow...
we will have to solve this equation
m-1 n-1 l-1
Σ Σ Σ 1
i=0 j=i+1 k=j+1
=
m-1 n-1
Σ Σ ( l - j -2)
i=0 j=i+1
m-1
Σ (l-2)*(n-i-2) - (n^2/2 - n/2 - i^2/2 + i/2)
i=0
Solve the last equation and you will get the actual answer.
According to Wolfram Alpha (wolframalpha.com), the sum you state is equal to 0.
http://www.wolframalpha.com/input/?i=sum+from+i%3D0+to+m-1+of+%28l-2%29*%28n-i-2%29+-+%28n%5E2%2F2+-+n%2F2+-+i%5E2%2F2+%2B+i%2F2%29
I did the algebra for these summations and got the same penultimate result, and then solved the final summation and got:
((m-1)*((n*l) - ((l*m)/2) - (2 * l) - ((3/2)*n) - ((1/4)*m) - 3 - ((n**2)/2) + (((2*(m**2)) - m)/6)))
However, this does not produce the same results as the code, unfortunately. For instance, m=2; n=4; l=6 produces -8 instead of the desired 14
summation over(n-1)(l-2)+(n-2)(l-3)+(n-3)(l-4)...(n-Z)(l-Z-1).... m times or till n-Z or l-Z-1 becomes negative
this has close form solution
summation (n-z)(l-z-1) = nl + z^2 +z - lz-nz-n
= nl + z^2 - (l+n-1)z -n
this summation can be calculated over 1-> Z
where Z = min(m,n,l-1)
the summation is
Zn(l-1) + Z*(Z+1)*( 2Z - 3l -3n +4)/6
Z=min(m,n,l-1)
test if any doubt
The answer is 1!+2!+---+ (l-2)!. I too could not find it directly. I had to debug and understand how the loop runs. It was completely dependent on the 'L' and not dependent on M and N. and by the way, since l-2 will be positive only when l>=3, the answer for l<=2 is 0.. for eg: if l = 6, then value is 1!+2!+3!+4! = 20..and for l=7 it will be 35.. and so on..
You can check it out..
Sorry i get the symbol wrongly.. i meant sum of integers not the factorial.. ∑(∑n) where n = 1 to l-2.. for the same example l = 6, sum of 1 to sum of 4..
Yes, I have already mentioned that case in the answer.. as l-2 will be positive only if l >2, the value will be 0 for any value of l that <= 2
mrange = min(m, l-2)
Σ[(l-i-2)(l-i-1)/2] from 1 to mrange
sum = mrange*(mrange+1)*(2*mrange+1)/12 + mrange*(mrange+1)*(1-2*l)/4 + mrange*l*(l-1)/2;
The closed form can be further reduced.
{
int ComputeFormula(const int& m, const int& n, const int& l) {
int mrange = std::min(m, l-2);
mrange = std::min(mrange, n-1);
int cstCorr = 0;
if(l > n) {
cstCorr = (l-n-1)*(l-n)/2;
}
return mrange*(mrange+1)*(2*mrange+1)/12 + mrange*(mrange+1)*(1-2*l)/4 + mrange*(l*(l-1)/2 - cstCorr );
}
}
This must work. Please challenge it.
In C++
// ConsoleApplication3.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
double Sum(int k, int l, int m)
{
double total = 0;
int x= min(l-1, m-1);
int y = min(x, k);
total = (y) * m * x - m*(y*(y-1))/2 - (y) * ((x+1)*(x+2)) / 2 + y * (( y * (y +1))/2) - ( ((y+1)* y * (2*y +1))/6 - (y*(y+1))/2);
return total;
}
int _tmain(int argc, _TCHAR* argv[])
{
int k = 1;
int l = 2;
int m = 3;
int sum = 0;
for(int i=0; i< k; i++)
for(int j= i+1; j< l; j++)
for(int z=j+1; z < m; z++)
sum++;
cout << sum << endl;
cout << Sum(k,l,m)<< endl;
getchar();
return 0;
}
Outputs
10
10
1. First of all the condition should be: {n > 1 and l > n}
2. After solving the summation: (sum from i=0 to m-1 (sum from j = i+1 to n-1 (sum from k = j+1 to l-1 {1} ))), the result would be:
sol = sol1 - sol2 + sol3/12 - sol4, where
sol1 = (((l*n)-l)-n+1)*m;
sol2 = l*m*(m-1)/2;
sol3 = (9*m*(m-1)) + (m-1)*m*(2*m-1);
sol4 = n*(n-1)*m/2;
This could be further simplified..
If the answer is negative, then the sum would be 0
should be 0 since for (int k = j + 1; k < l; k++) is never to execute that k always not ( k < 1 )
Dude: I think you didnt get the question the right way. The solution you have provided goes for these kind of loops:
Notice that the lengths of inner loops are not independent, these are depending on the iterating variables of the outer loops.
for (i = 0; i < m; i++)
for (j = 1; j < n; j++)
for (k = 2; k < l; k++)
sum++;
We will have to solve this equation:
- Sunny January 05, 2014m-1 n-1 l-1
Σ Σ Σ 1
i=0 j=i+1 k=j+1