A9 Interview Question for Software Engineer / Developers


Team: Search
Country: United States
Interview Type: In-Person




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

onestopinterviewprep.blogspot.com/2014/03/print-sub-matrix-with-equal-number-of.html

- codechamp March 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- kailashkaku1 March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

@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 ?

- kailashkaku1 March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Basically, don't post hearsay questions on the main site. Use the forum. Nothing wrong with that.

That's all.

- Anonymous March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@kailash: Your first comment ever, was on this. Do I smell a dirty sock puppet?

- Anonymous March 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Kailash. Like others you don't seem to understand.

THIS FUCKING SITE IS FOR FIRST HAND INTERVIEW QUESTIONS.

STOP FUCKING POLLUTING THIS SITE WITH RANDOM IRRELEVANT QUESTIONS.

IT IS A DETRIMENT TO SERIOUS JOB SEEKERS.

oops. caps locks was on.

- Anonymous April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- uuuouou March 31, 2014 | 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