## Microsoft Interview Question for Software Engineer Interns

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

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

The solution is here, rather, inverted.
geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

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

This can be solved by modifying binary search.

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

One way could be start processing from the center of the matrix. If value x you are searching for is less than mid (center of the matrix) then move to upper-left matrix, if value x is greater than mid then move to lower-right matrix. Stop when you find the element x or element is not there.

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

binary search first col, then binary search row

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

One possible approach is to start from top right corner and apply modified binary search

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

``````public static int[] findElement(int[][] matrix , int key)
{

int[] result=new int[2];
int col =matrix[0].length-1;

int row =0;

while(row< matrix.length && col >=0){

if(matrix[row][col]==key){
result[0]=row;
result[1]=col;
return result;
}
else if(matrix[row][col]>key){
col--;
}
else {
row++;

}

}

return result;
}``````

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

``````public static int[] findElement(int[][] matrix , int key)
{

int[] result=new int[2];
int col =matrix[0].length-1;

int row =0;

while(row< matrix.length && col >=0){

if(matrix[row][col]==key){
result[0]=row;
result[1]=col;
return result;
}
else if(matrix[row][col]>key){
col--;
}
else {
row++;

}

}

return result;
}``````

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

I see many of you do binary search, go to middle.
I check the row and column that the number locates at by comparing the number with the maximum of each row and column. Also, at the beginning, i check if the number is within the value range of matrix. At the end, must check if number found or not. I use range here, so must have the last if statement.
The worst case and avg. case is O(rows + columns).

int Search(int[][] matrix, int num)
{
if( num > matrix[matrix.length][matrix[0].length] }} num < matrix[0][0])
return 0;
int columnIndex = 0;
for(int index = 0; index < matrix[0].length; index++)
{
if(num > matrix[matrix.length][index])
columnIndex++;
else
break;
}
int rowIndex = 0;
for(int index = 0; index < matrix.length; index++)
{
if(num > matrix[index][columnIndex])
rowIndex++;
else
break;
}

if(matrix[rowIndx][columnIndex] == num)
return matrix[rowIndex][columnIndex];

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.

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

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