Amazon Interview Question for Software Engineer / Developers






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

- Anonymous February 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice efficient solution

- XeqtR February 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nick February 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- A February 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- XeqtR February 09, 2010 | Flag
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).

- Om February 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shri February 07, 2010 | Flag
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.

- Srisimil Dutta February 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is -ve numbers?

- Anonymous February 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

OMG!!

- Anonymous September 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# O(n)
def countneg(a):
    count = 0
    j = len(a[0])
    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

- Anonymous February 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- XeqtR February 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- XeqtR February 10, 2010 | Flag
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.

- sdm February 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i second this.

- ff February 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ryan February 20, 2010 | Flag
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[0][0] is >= 0, no. of -ve elements = 0;
3. if step 2 is not true, start from M[0][0] 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).

- cirus February 08, 2010 | Flag Reply
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.

- Amit February 10, 2010 | Flag Reply
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);
}

- Nishant February 15, 2010 | Flag Reply
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)

- yokuki February 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sdm March 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Yokuki March 16, 2010 | Flag
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 ); 
    } 
}

- durbin May 11, 2010 | Flag Reply
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; 
}

- Anonymous May 11, 2010 | Flag Reply
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[0].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[0].length)
j++;
count = count + j;
i++;
}
}
return count;
}
}
</pre><pre title="CodeMonkey91820" input="yes">1
2
10
42
11

</pre>

- Anonymous July 15, 2010 | Flag Reply
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[4][4] = 
					{
						{-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;
}

- Anonymous January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def countNegInRowColSortedMatrix(matr):
    row = 0;
    col = len(matr[0]) - 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);

- koustav.adorable July 15, 2017 | 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