## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
12
of 14 vote

We can do it using O[ mn ] space complexity & O[ (m-k)*(n-k) + mn] time complexity.

we can create a sum matrix of dimension (m x n) .
matrix [i][j] stores the sum of elements in input matrix of rows : 1 to i and cols: 1 to j.

Now to get the sum of elements in matrix in rows : i1 to i2 and cols : j1 to j2 ,
we can get this sum in O(1) time.

sum{ in[i1 to i2][j1 to j2] } = sum_Matrix[i2][j2] - sum_Matrix[i1-1][j2] - sum_Matrix[i2][j1-1] +sum_Matrix[i1 - 1][ j1 -1]

Now we can iterate in the Sum_Matrix to get the maximum amon all the k*k matrix elements sum.
This can be done in O( m-k * n-k)

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

Yes, this is another way of solving it. You should just say it's O(MN) -- that's still correct and is simpler.

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

As a example,

For input
1 2 1 3 4
2 1 3 1 4
1 5 6 7 8
1 2 1 2 1

Sum matrix is

1 3 4 7 11
3 6 10 14 22
4 12 22 33 49
5 21 26 39 55

if k=2, consider a matrix starts at location 2, 3

Then input value is
3,1
6,7
=17.

Corresponding sum matrix calculation is 33+3-12-7= 37-19 =17

Which is actually

=a[i+k-1][j+k-1]+a[i-1][j-1]-a[i+k-1][j]-a[i][j+k-1]

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

Please correct me if i'm wrong. But the answer of above should be 18. Considering the matrix 7,8
2,1

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

Infact 20. 1,4,7,8

Comment hidden because of low score. Click to expand.
8
of 10 vote

first add the k columns of each row like in robinkarp resulting in (m-k+1)*n;
now add the k rows of each column resulting in (m-k+1)(n-k+1);
find the highest element indx;
that will be the starting index of k*k matrix with highest sum O(m*n)

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

mrap rocks....

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

cool...

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

can u explain this approach a bit !!

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

3 2 1
5 6 4
1 2 3

sum columns

5 3
11 10
3 5

sum rows

16 13
14 15

find max -> 16

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

Awesome algo :) thanx for sharing it . giving correct results for all k*k

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

// This code has the order of O(n*m + (n-k)*(m-k)). But an extra array is needed.
public int maxMatSum(int[][] mat, int k) {
int res = 0;
int[][] num = new int[mat.length][mat[0].length];
int sum = 0;
for (int i = 0; i < mat.length; i++) {
sum += mat[i][0];
num[i][0] = sum;
}
sum = 0;
for (int j = 0; j < mat[0].length; j++) {
sum += mat[0][j];
num[0][j] = sum;
}
for (int m = 1; m < mat.length; m++) {
for (int n = 1; n < mat[0].length; n++) {
num[m][n] = mat[m][n] + num[m-1][n] + num[m][n-1] - num[m-1][n-1];
}
}
for (int m = 0; m < num.length - k; m++) {
for (int n = 0; n < num[0].length - k; n++) {
if(res < num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k]) {
res = num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k];
}
}
}
return res;
}

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

(Edited to reflect that there are 2 parameters, M and N, and the input is not just N*N).

We can do this in O(MN). High level outline:

1. Use a sliding window approach to create an auxiliary "sum matrix" where sum_matrix[i][j] = sum (input_matrix[i][j] + input_matrix[i][j + 1] + ... input_matrix [i][j+ k - 1]. By "sliding window", I mean that we should exploit the fact that sum_matrix[i][j] = sum_matrix[i][j - 1] + input_matrix [i][j+ k - 1] - input_matrix[i][j-1]. This reuse of previous results will allow the computation of the sum matrix in O(MN) time. (The sum matrix is of size m * (n-k), to avoid going out of bounds)

2. Now, the sum_matrix represents sums of k consecutive columns in the same row. So the remaining problem now is to find where in sum_matrix we get a maximum sum if we sum k consecutive rows in the same column. This can be done by a similar sliding window approach, again in O(MN) time.

Now we're done. The algorithm can be designed to just return the max sum or also keep track of where it was found. Since both steps above are O(MN), the algo is O(MN) overall. I should also mention that O(MN) is optimal because that is how much data we have, and we must look at all the data at least once.

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

How is step 2 O(M*N), i think it should be O(M*N*M) ( we have to consider all pair of rows to use sliding window approach )

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

Since the sum_array already has k-consecutive column sums, checking k consecutive rows in the same column of sum_matrix is checking k * k squares in the original input. You consider the columns one at a time in step 2, keeping track of where you saw the maximum as you go from column to column.

It is O(MN) as promised.

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

This problem can be solved by using dynamic programming, Let A be the matrix of size mXn , and we need to find maximum sum sub matrix,
Let us define S(i,j) = sum of elements in row i from column j to j+k-1 ,
we first calculate this S(i,j) for i from 1 to m and j from 1 to n-k+1
now we have vector sums for each row
Then we come to sub matrix sum which is sum of k row vectors
Let KSum(i,j) = sum of elements in sub matrix of size kXk with top left corner as A[i,j]
Then we can write
KSum(i,j) = KSum(i-1,j) - S(i-1,j) + S(i+k-1,j)
i<= i <= m-k+1
1<= j <= n-k+1

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

You can understand this solution by watching this tutorial youtu.be/siaRlAtip9I

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

I think dynamic programming is a little excessive here. Dynamic programming is most appropriate when you have subproblems whose solutions are re-used multiple times. Here there's no such thing. KSum(i,j) is only used in evaluating KSum(i+1, j).

You're better off just evaluating your recurrence iteratively. Of course you never say in your video how you intended to evaluate the recursion, so maybe your plan was to decompose it into iteration (and also not memorize solutions to subproblems, since that would also be a waste).

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

What is the complexity going to be? As far as i can see this is going to be expensive compared to first solution. When you i initialize the Sum array, its going to take O((m-k)*(n-k)) time to initialize it..

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

@ashutosh: So? How efficient do you think the top solution is? Like most other solutions on this page, it's O(m*n).

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

Leet, do you go for interviews every week? How come you come up with so many questions?

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

here we are just moving the matrix
first from 0,0 to k-1,k-1
then calculating the sum
we are having two more sums that are leftcolumnsum and top row sum
when we move the column
new sum = oldsum - leftcolumnsum+ new column(sum)

when we move by one row
new sum = oldsum - toprowsum + newrowaddedsum;

#include<iostream>
#include<stdlib.h>

using namespace std;

int main(){
int m=10;
int n=10;
int** array = (int**)malloc(sizeof(int*)*m);
// allocating the space to the array
for(int i=0;i<m;i++){
array[i] = (int*)malloc(sizeof(int)*n);
}

// initializing the array
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>array[i][j];
}
}
int topRowSum, leftColumnSum;
int k = 3;

// printing the array
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cout<<array[i][j]<<" ";
}
cout<<endl;
}
// we are checking for 3*3 matrix having the largest sum

int baseColumnSum;
int baseRowSum;
int baseSum;
int baseRow;
int baseColumn;
baseRow = 0;
baseColumn = 0;
baseSum = 0;
topRowSum = 0;
leftColumnSum = 0;

//initializing the base sum
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
baseSum += array[i][j];
}

}
baseColumnSum = baseSum;
baseRowSum = baseSum;

// initializing the top row sum and the left column sum
for(int i=0;i<k;i++){
topRowSum += array[0][i];
leftColumnSum += array[i][0];
}

// i,j corrospondes to the starting index of the square matrix
cout<<baseRowSum<<endl;
for(int i=0;i<(m-k);i++){

for(int j=1;j<=(n-k);j++){
baseColumnSum = baseColumnSum - leftColumnSum;
leftColumnSum = 0;
for(int m=0;m<k;m++){
baseColumnSum += array[i+m][k+j-1];
leftColumnSum += array[i+m][j];
}
if(baseColumnSum > baseSum){ //update the base values
baseSum = baseColumnSum;
baseRow = i;
baseColumn = j;
}
}// checking for a particular row and the all other columns
baseRowSum = baseRowSum - topRowSum;
topRowSum = 0;
for(int m=0;m<k;m++){
baseRowSum += array[k+i][m];
topRowSum += array[i+1][m];
}
cout<<baseRowSum<<endl;
if(baseRowSum > baseSum){
baseSum = baseRowSum;
baseRow = i+1;
baseColumn =0;
}
baseColumnSum = baseRowSum;
leftColumnSum = 0;
for(int m=0;m<k;m++){
leftColumnSum += array[i+1+m][0];
}
}

cout<<"maximum sum is"<<baseSum<<endl;
cout<<"i = "<<baseRow<<" j = "<<baseColumn<<endl;
return 0;

}

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

This code is working correct. Code is in C#. To verify just run it.

namespace MaxSumKxKMatrixInNxNMatrix
{
class Program
{
static void Main(string[] args)
{
int[,] abc= new int[5,6]{{6,4,7,2,-9,12} , {8, -2,5,3,1,9}, {9,3,1,8,5, -2}, {-2,4,6,8,10,12} , {1,3,5,7,-9,11} };
int[] ans = MaxKxKMatrix(abc, 5, 6, 3);

foreach (int item in ans)
{
Console.WriteLine(item);

}
}

static int[] MaxKxKMatrix(int[,] matrix, int n, int m, int k)
{
int[] max_mat_index = new int[3];
int max_sum = 0;

for (int i = 0; i <= n-k; i++)
{
for (int x = 0; x <= m - k; x++)

{
int row=0, col=0;
int this_matrix_sum = 0;
for (int j = i; j <= i+ k-1; j++)
{
for (int y = x; y <= x+k-1; y++)
{
this_matrix_sum = this_matrix_sum + matrix[j, y];
col = y;
}
row = j;
}
if (this_matrix_sum > max_sum)
{
max_sum = this_matrix_sum;
max_mat_index[0] = row;
max_mat_index[1] = col;
max_mat_index[2] = this_matrix_sum;
}
}
}
max_mat_index[0] = max_mat_index[0] - 2;
max_mat_index[1] = max_mat_index[1] - 2;
return max_mat_index;
}
}
}

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

@dc360,the questions are being asked to my friends

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

``````def findMaxKxK( matrix, k ):
print( matrix )
if k == 0 or len( matrix ) < k or len( matrix[0] ) < k :
print(  "Invalid k!" )
return None

m1_columns = len( matrix[0] ) - k + 1

m1 = []

for i in range( len( matrix ) ) :
m1.append( [0]*m1_columns )

for i in range( len( matrix ) ) :
for j in range( m1_columns ):
m1[i][j] = sum( matrix[i][j:j+k] )

m2 = []

m2_rows =  len( m1 ) - k + 1

for i in range( m2_rows ) :
m2.append( [0]*m1_columns )

for i in range( m2_rows ) :
for j in range( m1_columns ):
for iter in range( k ) :

i_max = 0
j_max = 0
max = 0

for i in range( m2_rows ):
for j in range( m1_columns ):
if m2[i][j] > max:
max = m2[i][j]
i_max = i
j_max = j

max_matrix = []

for i in range( k ) :
max_matrix.append( [0]*k )

for i in range( k ) :
for j in range( k ) :
max_matrix[i][j] = matrix[i_max+i][j_max+j]

print( str(k) + "_max = ", max_matrix )

return max_matrix

if __name__ == "__main__":
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0] ], 1 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 4 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 2 )
findMaxKxK( [ [3,2,1,0], [5,6,4,0], [1,2,3,0], [1,2,3,0] ], 0 )``````

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

There is no doubt that there will be (m-k) * (n-k) sub-matrix's of size k*k. Sum of a k*k matrix can be found in O(k * k). So, total time to get the max sum is O( (m-k) * (n-k) * k*k) which is O (mnkk) since k<m and k<n.

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

Traverse the matrix and keep inserting all elements of k*k matrix in an array. This traversal will be O(m*n). Now traverse the array, adding k*k elements and calculating max sum for those. For ex:

Matrix:
1 2 3
4 5 6
7 8 9

Array:
1,2,4,5,2,3,5,6,4,5,7,8,5,6,8,9
Sum of 1+2+4+5=12 (max_so_far)
next sum of 2+3+5+6=16(now max_so_far)

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.