## Interview Question

• 0

Country: United States

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

``````#include<stdio.h>
#include<conio.h>

int main()
{
int i,j,max=0,n,k,sum=0;
scanf("%d",&n);
int M[n][n],S[n][n],RS[n][n],CS[n][n],;
for(i=0;i<=n;i++)
{
M[i]=M[i]=S[i]=S[i]=RS[i]=RS[i]=CS[i]=CS[i]=0;

}
//this is to check boundary condition

for(i=1;i<=n;i++)
{

for(j=1;j<=n;j++)
{

scanf("%d",&M[i][j]);
RS[i][j]=RS[i][j-1]+M[i][j];
CS[i][j]=CS[i-1][j]+M[i][j];
S[i][j]=S[i-1][j-1]+RS[i][j]+CS[i][j]-M[i][j];
}
}

scanf("%d",&k);

//taken the size of sub matrix

for(i=k;i<=n;i++)
{
for(j=k;j<=n;j++)
{
sum=S[i][j]-S[i-k][j]-S[i][j-k]+S[i-k][j-k];
if(sum>max)
max=sum;
}
}

printf("%d\n",sum);

getch();
return 0;
}``````

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

I have used the technique called PREFIXSUM where the values of the Sum for various entries are saved while taking the input only.
RS[i][j]=sum of all the elements of the ith row upto jth entry

CS[i][j]=sum of all the elements of the jth column upto ith row

S[i][j]=sum of the matrix formed by the rectangle formed by the points {1,1}to {i,j}

M[i][j]=value stored in the ith row jth column

sum=sum of any sub array of kXk length
and each is found in constant time only.

So the performance is optimised as it is O(n^2).
space complexity is too O(n^2) actually 4(n^2),as extra space used for storage of RS[n][n],CS[n][n],S[n][n].

but the time is as good as taking the inputs O(n^2)

also to find the exact sub matrix store the value of sum in another arrray of nXn and the value of this matrix which is highest will give the maximum sum for that which can be found through BOTTOM UP approach or say if sum[x][y] is the highest then corresponding sub matrix will be the subMatrix formed by the M[x-k+1][y-k+1] to M[x][y]

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

is this the viola and jones algorithm? sounds very familiar to me

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

But you are considering only the submatrices starting in (1,1), isn't it? If in the problem you need to consider all possible submatrices (ie, starting at other indices), I don't see how you can have less than O(n^4)

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

@crazydev I'm getting the sum done by subtracting through the indices of the matrices that are of kxk
read the code all has been explained it will work in O(n^2) time only!!!!

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

Here is my solution. It is inspired by the classic problem of finding max subarray in 1D array. Here the program tries to find a max submatrix which ends at {i,j}. Then the max submatrix should be the maximum among the max submarices ending at all i's and j's.

To search {i,j} start at j=0, for each i, it needs O(n) to find a max submatrix for each {i,j},
for j>0, the results from j-1 can be used which is basically in a DP way.

Overall complexity should be O(n^3)

``````#include<stdlib.h>
#include<stdio.h>
#define N 9
#define AT(a,b,c) (*((a)+(b)*N+(c)))
void findMaxEnd(int *a,
int *max,int *max_i, int *max_end,
int i,int j,
int *maxe, int *max_height, int *max_posi)
{
int height;
int pos=i;
int hi;
int s=0;
*maxe=-999999;
for (hi=i;hi>=0;hi--)
{
s+=AT(a,hi,j);
AT(max_end, pos, i-hi)+=s;
if (s>AT(max_end, pos, i-hi))
{
AT(max_end, pos, i-hi)=s;
AT(max_i,pos,i-hi)=j;
}
if (*maxe<AT(max_end,pos,i-hi))
{
*maxe=AT(max_end,pos,i-hi);
*max_height = i-hi;
*max_posi = AT(max_i,pos,i-hi);
}

}

}

int main()
{
int a_0[N*N]={
10,10,1 ,23,-4, 5, 6,23, 7,
-6,10,12,3 ,-4, 5,-3,10, 7,
10,10,-200,23,-4,-200, 6,23,-7,
-2, 3,1 ,99,99, 5,32, 0,-7,
10, 4,1 ,99,99, 5, 6,-5,-7,
3 , 5,1 ,99,99,-5,-3,-5, 7,
18,-6,1 ,23,-4,-200, 6,4 , 7,
2 ,10,1 ,-2,14, 5,10,10, 7,
2 ,10,1 ,23,-4, 5, 2,2 , 7
};
int s_0[N];
int max_0[N*N], max_i0[N*N], max_end0[N*N];
int *a=a_0,*s=s_0,*max=max_0,
*max_i=max_i0,*max_end=max_end0;
int maxe,max_height,max_posi;
int all_maxe=-999999, all_max_height, all_max_posi,
all_i=-1, all_j=-1;
int i,j;

for (i=0;i<N;i++)
for (j=0;j<N;j++)
{
AT(max_end,i,j)=-999999;
AT(max_i,i,j) = 0;
}

for (j=0;j<N;j++)
for (i=N-1;i>=0;i--)
{
findMaxEnd(a,max,max_i,max_end,i,j,&maxe,&max_height,&max_posi);
printf("%d %d %d %d %d\n",j,i,maxe,max_height,max_posi);
if (all_maxe<maxe)
{
all_maxe=maxe;
all_max_height=max_height;
all_max_posi=max_posi;
all_i=i;
all_j=j;
}
}
printf("Max submatrice:\n");
for (i=all_i-all_max_height;i<=all_i;i++)
{
for (j=all_max_posi;j<=all_j;j++)
printf("%5d",AT(a,i,j));
printf("\n");
}

return 0;
}``````

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.