Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
void test18()
{
int A[4][4] = { {1,5,3,8}
, {7,3,1,8}
, {8,3,5,9}
, {8,3,5,1} };
int B[4][4] = {0x00};
for( size_t i = 0; i < 4; i++ )
{
for( size_t j = 0; j < 4; j++ )
{
int left = (j > 0 ? B[i][j-1] : 0) ;
int upper = (i > 0 ? B[i-1][j] : 0);
int sum = left + upper + A[i][j];
B[i][j] = sum;
}
}
for( size_t i = 0; i < 4; i++ )
{
cout << B[i][0] << ", " << B[i][1] << ", " << B[i][2] << ", " << B[i][3] << "\n";
}
}
I think, to calculate the sum it should be like this:
int sum = left + upper + A[i][j] - B[i-1][j-1];
more efficient code which skips the two conditions in the inner most loops.
#include<stdio.h>
#include<stdlib.h>
int main()
{
int A[4][4]={{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};
int m = 4 , n = 4, i, j;
int sum[m][n];
sum[0][0]=A[0][0];
sum[1][0]=sum[0][0] + A[1][0];
sum[0][1]=sum[0][0] + A[0][1];
for(i=0;i<m;i++) {
for(j=0;j<n;j++)
printf("%d ",A[i][j]);
printf("\n");
}
printf("====================\n");
for(i=1;i<m;i++)
sum[i][0]=sum[i-1][0] + A[i][0];
for(j=1;j<m;j++)
sum[0][j]=sum[0][j-1] + A[0][j];
for(i=1;i<m;i++)
for(j=1;j<n;j++)
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + A[i][j];
for(i=0;i<m;i++) {
for(j=0;j<n;j++)
printf("%d ",sum[i][j]);
printf("\n");
}
return 0;
}
Maybe I am wrong but this seems pretty simple and only needs 2 for loops and a running total... Here is the psuedo code:
m = original matrix
newM = new matrix
runningTotal = the sum of all the elements till that point
for( i < 0; i < m[0].size; i++)
for( j< 0; j < m.size; j++)
runningTotal += m[i][j];
newM[i][j] = runningTotal;
Yes you are right, that you are wrong.
Let us take a small array, none of us has time to rectify your bullshit mistakes.
A = { { 1 , 2 } , { 3 , 4 } }
The array which will be created by your algo is the following :
newM = { { 1 , 3 } , { 7 , 11 } }
void sumMatrix()
{
int a[][4]=\
{
{1,5,9,13},
{2,6,10,14},
{3,7,11,15},
{4,8,12,16}
};
int b[4][4]= {0,};
for(int i = 0;i<4;i++)
{
int sum = 0;
for(int j = 0;j<4;j++)
{
int k = 0;
while(k<=i)
{
sum = sum + a[k][j];
k++;
}
b[i][j] = sum;
}
}
//displaying the matrix...
cout<<"displaying original matrix..."<<endl;
for(int i = 0;i<4;i++)
{
for(int j = 0;j<4;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
//displaying sum matrix...
cout<<"displaying sum matrix..."<<endl;
for(int i = 0;i<4;i++)
{
for(int j = 0;j<4;j++)
{
cout<<b[i][j]<<" ";
}
cout<<endl;
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i ==0 && j == 0){
sumMatrix[i][j] = matrix[0][0];
}else if (i==0){
sumMatrix[i][j] = sumMatrix[i][j-1] + matrix[i][j] ;
}else if(j==0){
sumMatrix[i][j] = sumMatrix[i-1][j] + matrix[i][j] ;
}else{
sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sumMatrix[i-1][j-1] + matrix[i][j] ;
}
}
}
1. Error checks - make sure m is not null and m has more than one element
- prolific.coder May 19, 20122. Iterate over M and populate the numbers sum into a variable sum.
3. let x = m.getlength(0) and y= m.getlength(1)
3. Create a new matrix out and populate out[x][y] with sum
4. Create a decreasing loop from x,y to 0,0 and populate with the following formula
out[i][j]=sum-m[i][j]