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)

- Navin August 12, 2012 | Flag Reply
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.

- eugene.yarovoi August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- hari@hbiz.in August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shivam August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Infact 20. 1,4,7,8

- Shivam Maharshi August 14, 2012 | Flag
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)

- check.it August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

mrap rocks....

- Anonymous August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool...

- geek August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u explain this approach a bit !!

- Anonymous August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- the | Coder September 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tuhinjubcse January 25, 2013 | Flag
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;
}

- Shivam Maharshi August 14, 2012 | Flag Reply
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.

- eugene.yarovoi August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 )

- Cerberuz August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi August 12, 2012 | Flag
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

- saurabh August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- eugene.yarovoi August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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..

- godzilaa August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi August 15, 2012 | Flag
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?

- dc360 August 17, 2012 | Flag Reply
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;


}

- Anonymous August 13, 2012 | Flag Reply
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);

}
Console.ReadLine();
}


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;
}
}
}

- VolVo August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@dc360,the questions are being asked to my friends

- grave August 19, 2012 | Flag Reply
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 ):
            add = 0
            for iter in range( k ) :
                add = add + m1[i+iter][j]
            m2[i][j] = add
    
    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 )

- the | Coder September 08, 2012 | Flag Reply
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.

- AKA August 12, 2012 | Flag Reply
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)

- Anonymous August 25, 2012 | Flag Reply


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