## Amazon Interview Question for Software Engineer / Developers

• 0

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

int countNegatives(int array[][], int size) {
int col = size - 1, row = 0;
int count = 0;

while(row < size && col >= 0) {
if(array[row][col] < 0 ) {
count = count + (col + 1);
row = row + 1;
}
else {
col = col - 1;
}
}
return count;
}

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

Nice efficient solution

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

@Anonymous
Yes...this is the solution that I gave initially. I guess this solution can be further optimised using binary search

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

Worst case is O(n^2) when all the negative elements are in the first column.....
binary search on each row or column will give O(nlogn)

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

@Anonymous
please try to run this soln on any example..
count = count + (col + 1);
????????????????

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

@A
hows the worst case O(n^2) when all negative elements are in the first column? In that case it would be O(n+n-1) which O(n).
@above
count= count + (col+1) .. tht s cause if at a specific col value a number is neg the numbers on the same line i.e. row in all prev cols are neg too as it is sorted..

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

@A
hows the worst case O(n^2) when all negative elements are in the first column? In that case it would be O(n+n-1) which O(n).
@above
count= count + (col+1) .. tht s cause if at a specific col value a number is neg the numbers on the same line i.e. row in all prev cols are neg too as it is sorted..

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

Assume the elements in the row and the column are sorted in increasing order.

Case 1: Now compare the element [0,0].. if it is greater thean zero.. it means all the elements are +ve.. so number of negetive integers=0\

Case: if [0.0] element is a -ve number.
In this case, we will start our search from [n,n].. if array[n,n] is -ve.. it means all the numbers in the array are negetive. If array[n,n] is +ve, then move a level up diagonally, i.e move to [n-1,n-1]... move up one level till u find a -ve number. If suppose we find a -ve number at [i,i] it means all the numbers in that square matrix with indices i,i are -ve. Now will have to only check for the next column and next row for the number of -ve numbers. So, if we have a -ve number at [i,i], then number of -ve numbers in the array = i*i + (number of -ve elenments in row i+1) + (number of -ve elenments in column i+1). this can be doen in O(n).

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

hmm fails in matrix like
-5 0 1
-2 1 2
-1 2 3

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

Finding the first negative number at [i,i] only means that the sub-matrix with row and column indices from i through n has only one negative element. We shouldn't ignore other elements, say the element at [m,n] where m<i, n>i. For example,
The above algorithm will not work for the following case.
Assume n=4 and the matrix is
-30, -29, -28, -27
-29, -28, +30, +40
+30, +40, +50, +60
+44, +55, +65, +75
Applying the above algorithm will result in i=2. So, according to the given algorithm, number of negative elements will be
(2*2) + (no. of negative elements in row 3) + (no. of negative elements in column 3)
= 4 + 0 + 1
= 5
But, the last element in first row is unaccounted for.

My algorithm is as follows.
Do a binary search for the first positive number in every row. If the index is i, the number of negative elements in that row will be i-1.
Do this for all the n rows. Complexity is (n * log(n)).
Perhaps we can merge this and the above idea to produce an even better algorithm.

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

what is -ve numbers?

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

OMG!!

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

``````# O(n)
def countneg(a):
count = 0
j = len(a)
for i in xrange(len(a)):
while j > 0 and a[i][j - 1] >= 0:
j -= 1
count += j
return count

mat = [[-5, 0, 1], [-2, 1, 2], [-1, 2, 3]]
print countneg(mat)
# 3``````

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

If n is the number of elements in a row or column then ur algorithm is O(n^2).. the above solutions seem to have O(nlogn) in that case.. Going to each element is surely not an efficient solution.. ur not making use of the sorted property..

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

Naa.. I was mistaken.. This is similar to the post below that I praised.. O(n) it is

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

How about doing binary search for finding the first positive in a row a, say at (i,j) and then eliminating submatrix of positives (n-i,n-j). And then moving to next row and doing the same.
Worst case would still be nlogn if there are no positives at all in the matrix.

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

i second this.

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

O(n log n) is inferior to O(n), which is the runtime of the solution already given above.

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

My take:
1. start from topmost and leftmost element of matrix M.
2. As a post above mentions, iff M is >= 0, no. of -ve elements = 0;
3. if step 2 is not true, start from M and search non-negative no. row wise.
3a. On finding first non-negative no. , mark the corresponding column number.
Elements in that column are all non-negative.
3b. Let say a non-negative no. is found at column (m+1). Then for each of the remaining rows, search operation is to be performed till m column.
3c. In this case worst case search will be O(mn).

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

My solution is:
1) scan first row till you don't find a positive number. Suppose you found it at a[m][n].
2) Now check a[m+1][n] element.
a)If it is -ve then go to next row but same column till you don't find +ve or end.
b) If it is +ve then scan left until you can't find -ve.

Repeat step 2.

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

This is an elegant solution
public static void main(String[] args) {
int [][] a = new int[][] {{-30,-29,-28,-27},{-29,-28,30,40},{30,40,50,60},{44,55,65,75}};
int n = 4;
int i = 0;
int j = n-1;
int sum = 0;
while(j>-1 && i<n)
{
if(a[i][j]<0)
{
sum = sum + j+1;
i++;
}
else
{
j--;
}
}
System.out.println(sum);
}

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

Algorithm:
1. Search for an element M(a, b) on the diagonal of Matrix(n * n) that all M(i,j) that i<a, j<b has M(i,j)>0 and all M(i,j) that i>a, j>b has M(i, j)<0.
Search for element M(a, b) will take O(lgn) time.
2. Add the size of Matrix(n-a, n-b) to the total count
3. Divide the original Matrix into two subMatrixes M1=M(a to n, 0 to b) and M2=M(0 to a, b to n)
4. Do step 1-3 recursively to M1 and M2 till M1 and M2 could not be found any more.

Worst Case Time complexity: T(n) = 2T(n/2) + lg(n) = O(n)

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

If the sub-matrices are not square, how will step 1 be carried out on them?

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

It doesn't matter if the sub-matrices are square or not. We just need to find a position (a,b) on the diagonal which satisfy M(i,j) that i<a, j<b has M(i,j)>0 and all M(i,j) that i>a, j>b has M(i, j)<0.
For a sub-matrix which is not a square, you may get a search point (5/2, 3), then just search both (2,3) and (3,3) -- it's still constant time.

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

``````int FindNegative(int M[][], int top, int left, int bottom, int right)
{
if (top <= bottom && left <= right)
{
int center = M[(top + bottom)/2][(left+right)/2];
if (center > 0)
{
return FindNegative(M, top, left, (top+bottom)/2, (left+righ)/2) +
FindNegative(M, top, (left+right)/2 + 1, (top+bottom)/2 -1, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 -1);
}

return ((top+bottom)/2 +1 )*((left + right)/2+1) +
FindNegative(M, top, (left+right)/2 + 1, bottom, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 );
}
}``````

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

``````int FindNegative(int M[][], int top, int left, int bottom, int right)
{
if (top <= bottom && left <= right)
{
int center = M[(top + bottom)/2][(left+right)/2];
if (center > 0)
{
return FindNegative(M, top, left, (top+bottom)/2, (left+righ)/2) +
FindNegative(M, top, (left+right)/2 + 1, (top+bottom)/2 -1, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 -1);
}

return ((top+bottom)/2 +1 )*((left + right)/2+1) +
FindNegative(M, top, (left+right)/2 + 1, bottom, right) +
FindNegative(M, (top+bottom)/2+1, left,bottom, (left+right)/2 );
}
return 0;
}``````

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

<pre lang="java" line="1" title="CodeMonkey91820" class="run-this"> class CountNegative {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] aMatrix = { { -9, -3,- 2, 120 }, { -8, -2, 30, 230 },
{ -7, -1, 40, 420 }, { -6, 90, 91, 520 } };
int negCount = countNegative(aMatrix);
System.out.print(negCount);
}

private static int countNegative(int[][] aMatrix) {
// TODO Auto-generated method stub
int i = 0;
int j = aMatrix.length - 1;
while (aMatrix[i][j] >= 0 && j > 0)
j--;

if (j < 0)
return 0;
int count = j + 1;
i++;
while (i < aMatrix.length) {
if (aMatrix[i][j] >= 0) {
j--;
} else {
while (aMatrix[i][j] < 0 && j < aMatrix.length)
j++;
count = count + j;
i++;
}
}
return count;
}
}
</pre><pre title="CodeMonkey91820" input="yes">1
2
10
42
11

</pre>

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

``````#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int a =
{
{-15, -10, 4, 6},
{-10, -3, 7, 10},
{-5, -1, 12, 15},
{-3, -2, 15, 20}
};

int m=4, n=4, num=0, count=0;
for(int i=0, j=n-1; i<m && j>=0; )
{
if(num > a[i][j])
{
i++;
count += (j+1);
}
else
j--;
}

cout << count << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````def countNegInRowColSortedMatrix(matr):
row = 0;
col = len(matr) - 1;
countNeg = 0;
while(row < len(matr) and col >= 0):
while col >= 0 and matr[row][col] >= 0 :
col = col - 1;
countNeg = countNeg + col + 1;
row = row + 1;
return countNeg;

matr = [[-100, -20, -10],
[-5, -7, 0],
[-4, -2, 42]];
print countNegInRowColSortedMatrix(matr);``````

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.