## Microsoft Interview Question for Software Engineer / Developers

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

Approach: Assuming indexes in the range 1...N,start at (1,N) ,i.e. right hand top and check if the element is negative.If yes,obviously all the elements on its left including itself would be -ve.So set the count_of_negatives to N and increment the row_index.If a(1,N) is >=0,decrement the col_index.

So at any general grid point , if a(row,col)< 0, increment row by 1 and count_of_negatives by col,because all the elements to the left of a(row,col) including itself in the same row would be < 0. On the other hand if a(row,col) >=0, just decrement col. Execute the above in a loop till you transcend the boundaries of the matrix.

Time Complexity is 2n which is O(n),where n is number of rows(cols) in the square matrix

The pseudocode is

numNegatives(a[1..N][1...N]){

if a(1,1) >= 0 return 0;

if a(N,N) < 0 return N*N;

row = 1
col = N
count = 0; //count is the number of negatives in the matrix
while( row <=N && col >= 1 ){
if(a(row,col) < 0){
count += col; //everything on the left of a(row,col)including itself are -ve
row++;
}else{
col--;
}
}

return count;
}

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

Perfect code! :-)

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

bingo!

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

Thanks for those kind remarks :)

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

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

Nice solution!

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

wonderful!

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

sorry it's not O(n)complexity. In the worst case you check all the n^2 elements of the matrix and so it's o(n^2). Instead we can do binary search on every row to make it O(nlog n). I wonder if we can make it run faster

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

Raj, why do you think worst case will be O(n^2)? The question simply asks for finding the number of negative elements.

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

The solution suggested by random does not work if we start from top right edge of the matrix, but it works fine if we start from bottom right and move upwards towards [0,0] element. Here is updated code

``````public int CountNumberofNegativeNumbersInASortedMatrix()
{
int N = 5;
int [,] arr =
{
{ -3, -2,  3,  4,  5},
{ -4, -3,  2,  3,  4},
{ -5, -4, -1,  1,  2},
{ -6, -5, -2,  0,  1},
{ -7, -6, -3, -2, -1},
};

if ( arr[0,0] >= 0 )
return 0;

if ( arr[N -1 ,N -1] < 0 )
return N -1 * N - 1;

int row = N - 1;
int col = N - 1;
int count = 0; //count is the number of negatives in the matrix
while( row >= 0  && col >= 0 )
{
if(arr[row,col] < 0)
{
count += col + 1 ; //everything on the left of a(row,col)including itself are -ve
row--;
}
else
{
col--;
}
}
return count;
}``````

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

abe chutia its depends upon how your array is sorted.

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

In the worst-case, if there are no negative elements in the matrix, you need to traverse all rows and all columns and thus the complexity becomes O(n^2)

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

I also thought same Solution in O(n) .

@Ashwin, if all elemtns are +ve , that case also time complexity is O(n).

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

rough idea:

M row, N column

1.start from right-bottom corner, go up and check the 1st element <0, if not found, proceed to next column
2.when the 1st elem that < 0 is found, record it - say (i,j), and go downward to (i-1,j) and then go left and check the 1st elem <0;

repeat 1,2 and we are basically tracking the right-bottom position of the area with all -ve numbers.

worst case O(MN),

improvement can be done by using binary search when checking the 1st -ve number at each row/column

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

``````static class Program
{
// Test data.
static int[,] array = { { -2, -1, 3 }, { -1, 0, 4 }, { 1, 3, 5 } };

// Counts the number of negative elements in a given (sub)rectangle.
static int CountNegatives(int row, int col, int rowCount, int colCount)
{
// Make sure the area is not empty.
if (rowCount == 0 || colCount == 0)
return 0;

// Check the bottom-right (largest) element.
if (array[row + rowCount - 1, col + colCount - 1] < 0)
return rowCount * colCount; // all numbers are negative

// Check the top-left (smallest) element.
if (array[row, col] >= 0)
return 0;   // all numbers are positive

// Divide the area into 4 sub-rectangles and process them recursively.
int dRow = rowCount / 2;
int dCol = colCount / 2;
return
CountNegatives(row, col, dRow, dCol) +
CountNegatives(row + dRow, col, dRow, dCol) +
CountNegatives(row, col + dCol, dRow, dCol) +
CountNegatives(row + dRow, col + dCol, dRow, dCol);
}

static void Main(string[] args)
{
System.Console.WriteLine(CountNegatives(0, 0, array.GetLength(0), array.GetLength(1)));
}
}``````

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

it is no way O(logN).
Suppose N= 2^k.

You get c * (2 + 2*2 + 2* 2^2 + ...+ 2^K)= c*2^(K+1)=2c*N
where c is some overhead number.

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

This solution can be described by the following recurrence:
T(n) = 4T(n/4) + O(1) and according to master theorem it is an O(n) solution.

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

^ there's an obvious bug there (the rightmost column and the bottom row will be sometimes lost because of the integer division by 2), but I guess the algorithm should work once that bug is fixed.

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

``````// Divide the area into 4 sub-rectangles and process them recursively.
int dRow = rowCount / 2;
int dCol = colCount / 2;
int rRow = rowCount % 2;
int rCol = colCount % 2;
return
CountNegatives(row, col, dRow, dCol) +
CountNegatives(row + dRow, col, dRow + rRow, dCol) +
CountNegatives(row, col + dCol, dRow, dCol + rCol) +
CountNegatives(row + dRow, col + dCol, dRow + rRow, dCol + rCol);``````

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

Given the array, a[n][n],the negative num is Num(Num=0 initally) from the right-top corner, a[0][n-1], check whether it >0 or not, if >=0, move to the lefter one, a[0][n-2], if it < 0, found the first element which >=0 in the same column, suppose it is a[x][n-1], Num+=x*n, Move to the a[x][n-2], do the similar things untill the current element move outside the array. The time complexisty is O(n)

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

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

start with the top right element ...if no neg decrement the col iterator..
if neg means incr count col iterator times..incr the row iterator..repeat till the last row or first col is reached...O(m+n)

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

The above algorithm assumes it is sorted in the same order(all increase or decrease).

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

``````function CountNegatives(arr, row, col):
count = 0
for(i = col, j = 1; i >= 1 and j <= row):
if(arr[j][i] > 0):
i--
else
count += i
j++
return count``````

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

#include<iostream>
using namespace std;

int findNeg(int Arr[][3])
{
int count = 0,COL=3;
for(int i=0;i<3;i++)
{
if(Arr[i][0]>0)
break;
for(int j=0;j<COL;j++)
{
if(Arr[i][j]>0)
{
COL = j;
break;
}
count++;
}
}
return count;
}

int main()
{
int arr[3][3] = {{-3,-2,-1},{-2,1,3},{1,2,4}};
cout <<"Number of Negative numbers = " <<findNeg(arr);
return 0;
}

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

http: //webcourse . cs.technion.ac.il/234247/Spring2006/ho/WCFiles/Celebrity . pdf

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

Guys,
Well, it is definitely O(N) solution. One outstanding property is a diagonal property. So to say, Let cell X = (k,k) be a diagonal cell. No other cell (i,j); i < k, and j < k has a value greater than X. Then the solution is move diagonally from (0,0) bottom-right. Find the last diagonal that still negative, then we are guarantee to have at least (k-1)^2 negative cells. Then count the negative number in column k and row k. The time complexity is sqrt(2N^2) + 2N = O(N).

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

error: we have at least k^2 negative cell not (k-1)^2, then count the negative number in the column k+1 and row k+1. Sorry guys.

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.