Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
convolve the original matrix with the matrix of ones (Kernel) and fing the max value of the 2D matrix. which will return the center position of the submatrix with the largest sum.
Size of the kernal will decide the size of the sunMatrix.
in matlab it can be done like this
orignal2DMatrix;
subMatKernal = ones(sizeOfSubMatrix,sizeOfSubMatrix);
result = conv2(orignal2DMatrix,subMatKernal );
matrixIndex= find(max(result));
Logic:
Step 1:
Row wise operation:
Replace the matrix data with the sum of element in row upto current column number.
Replace A[x,y] = A[x,0]+A[x,1]+A[x,2]+A[x,3]+......+A[x,y]
If A =
[1 2 3]
[4 5 6]
[7 8 9]
then after first step:
A=
[1 3 6]
[4 9 15]
[7 15 24]
Step 2:
Column wise operation:
Replace the matrix data with the sum of element in column upto current row number.
Replace A[x,y] = A[0,y]+A[1,y]+A[2,y]+A[3,y]+......+A[x,y]
Now A =
A=
[1 3 6]
[5 12 21]
[12 27 45]
Step 3:
Now find the max diff b/w to A[x,y]-A[x',y'] elements in the result matrix where
X>=X' and
Y>=Y'
Check "Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)" on geeks for geeks site.
- 42 May 21, 2014