A9 Interview Question
Software Engineer / DevelopersTeam: Search
Country: United States
Interview Type: In-Person
@Anonymous, y r u being such a loser. Is he troubling u in any way. If it is of any use to u, click on d question else not. and looks lik u r a complete jobless person lol.
@codechamp, U r also spamming a lot as I see. stop doing it.
@latrolla, on wat basis u say these questions r irrelevant ? I agree this may not be a firsthand queation. To be frank I had never come across this question, so it helped me in a way. Detriment to job seekers ?? lol r u serious ?
@kailash. LOL, you are clueless.
Interview questions are of a specific difficulty level. Any Homework/Programming contest/algorithm puzzle does not cut it.
I take it you have no experience being an interviewer in a company like Microsoft? Heck, I bet you haven't even been in some interviewer training course given in such companies.
Such questions are
1) A waste of time
2) Give people the wrong impressions about what interview questions are really like.
3) Might get people to spend time studying the wrong things.
FUCKINGIDIOTSONTHISSITE.AND.SOCKPUPPETS.
Basically, don't post hearsay questions on the main site. Use the forum. Nothing wrong with that.
That's all.
(1)For M*N matrix, brute force has O(1) space complexity and O(M*M*M*N*N*N) time complexity for enumerating every submatrix then counting ones and zeros inside.
(2)Following is a method that has O(M*N) space complexity and O(M*M*N*N) time complexity:
public class ZerosOnesMatrix {
static public void printSubMatrix(int leftUpRow, int leftUpCol, int rightDownRow, int rightDownCol, int[][] matrix){
System.out.println("(" + leftUpRow + "," + leftUpCol + ") => (" + rightDownRow + "," + rightDownCol + ")");
for(int i = leftUpRow; i <= rightDownRow; ++i){
for(int j = leftUpCol; j <= rightDownCol; ++j){
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
static public void printSubmatrixWithEqualZerosAndOnes(int[][] matrix){
int M = matrix.length, N = matrix[0].length;
/*
* step 1: create memory for submatrix with left up being (0, 0)
* first dimension is submatrix's right down row
* second dimension is submatrix's right down col
* count[][][0] is this submatrix's count of zeros
* count[][][1] is this submatrix's count of ones
*/
int[][][] count = new int[M][N][2];
/*
* step 2: initialize first row's count and first col's count
*/
count[0][0][0] = matrix[0][0] == 0 ? 1 : 0;
count[0][0][1] = matrix[0][0] == 0 ? 0 : 1;
for(int col = 1; col < N; ++col){
count[0][col][0] = count[0][col-1][0];
count[0][col][1] = count[0][col-1][1];
++count[0][col][matrix[0][col]];
}
for(int row = 1; row < M; ++row){
count[row][0][0] = count[row-1][0][0];
count[row][0][1] = count[row-1][0][1];
++count[row][0][matrix[row][0]];
}
/*
* step 3: enumerate each submatrix with left up being (0, 0)
* and calculate its count of ones and zeros
*/
for(int row = 1; row < M; ++row){
for(int col = 1; col < N; ++col){
count[row][col][0] = count[row-1][col][0] + count[row][col-1][0] - count[row-1][col-1][0];
count[row][col][1] = count[row-1][col][1] + count[row][col-1][1] - count[row-1][col-1][1];
++count[row][col][matrix[row][col]];
}
}
/*
* step 4: enumerate every submatrix and check its count of ones and zeros
*/
int[] subCount = {0, 0};
for(int leftUpRow = 0; leftUpRow < M; ++leftUpRow){
for(int leftUpCol = 0; leftUpCol < N; ++leftUpCol){
for(int rightDownRow = leftUpRow; rightDownRow < M; ++rightDownRow){
for(int rightDownCol = leftUpCol; rightDownCol < N; ++rightDownCol){
for(int i = 0; i < 2; ++i){
subCount[i] = count[rightDownRow][rightDownCol][i] -
(leftUpRow > 0 ? count[leftUpRow-1][rightDownCol][i] : 0) -
(leftUpCol > 0 ? count[rightDownRow][leftUpCol-1][i] : 0) +
(leftUpRow > 0 && leftUpCol > 0 ? count[leftUpRow-1][leftUpCol-1][i] : 0);
}
if(subCount[0] == subCount[1]) printSubMatrix(leftUpRow, leftUpCol, rightDownRow, rightDownCol, matrix);
}
}
}
}
}
static public void main(String[] args){
int matrix[][] = {
{0, 1, 0, 1, 0},
{0, 0, 1, 1, 0},
{0, 0, 0, 0, 1},
{1, 0, 1, 0, 0}
};
printSubmatrixWithEqualZerosAndOnes(matrix);
}
}
onestopinterviewprep.blogspot.com/2014/03/print-sub-matrix-with-equal-number-of.html
- codechamp March 30, 2014