Microsoft Interview Question 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;
}

- random on December 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect code! :-)

- gamer on December 16, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bingo!

gr8 answer

- fuzzy on December 16, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for those kind remarks :)

- random on December 16, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

really good answer!!!!

- tb on January 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution!

- spsneo on January 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wonderful!

- srini on February 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Raj on March 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on March 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anunay on June 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

abe chutia its depends upon how your array is sorted.

- Gaurav.Singh on November 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Ashwin on February 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also thought same Solution in O(n) .

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

- siva.sai.2020 on May 27, 2012 | Flag
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

- Anonymous on December 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would start with this. I wonder about complexity - is it really O(log N)?

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

- Netspirit (MSFT) on December 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kulang on December 15, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- pt4h on April 21, 2010 | Flag
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.

- Netspirit (MSFT) on December 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

// 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);

- Anonymous on December 13, 2009 | Flag
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)

- Guyi.hero on December 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Was this asked in microsoft....?for what position?nice ques though

- Anonymous on December 14, 2009 | Flag Reply
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)

- sg on December 14, 2009 | Flag Reply
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).

- kulang on December 15, 2009 | Flag Reply
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

- Thiyanesh on December 16, 2009 | Flag Reply
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;
}

- Gajanan on December 17, 2009 | Flag Reply
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

- Anonymous on January 03, 2010 | Flag Reply
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).

- saimok on May 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- saimok on May 02, 2010 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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