## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

Here is a working code in C. The complexity is of O(n).

``````#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#define COL 4
#define ROW 4
using namespace std;
int main()
{
int arr[ROW][COL]= {
{1,1,1,1},
{1,1,0,0},
{1,0,0,0},
{1,1,0,0},
};

int rownum;
int i = 0, j = COL-1;
while(i<ROW && j>0)
{
if(arr[i][j]==0)
{
j--;
rownum=i;}
else
i++;
}
printf("%d",rownum);
getch();
return 0;``````

}

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

Nice solution...

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

Nice solution...

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

you can improve running time a little by applying binary search on each row, so ur running time will reduce from O(Row+Col) to O(LogRow + Col)

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

how u r getting d complexity as O(n)?u r running two loops.one changing i in each iteration and one loop running 'j'..in worst case complexity becomes o(n^2)..i think so..

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

how u r getting d complexity as O(n)?u r running two loops.one changing i in each iteration and one loop running 'j'..in worst case complexity becomes o(n^2)..i think so..

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

I think there is only one loop - while loop. In any case it runs for min(row,col-1) times. Complexity in worst case is o(n) only.

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

Possible bug in code for below test case. Correct answer for this case should be rownum = 3, code returns 2.

``````{1,1,1,1},
{1,1,0,0},
{1,0,0,0},
{0,0,0,0},
}``````

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

while(i<ROW && j>0) ,just change to j>=0

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

simple and nice solution!

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

Your code will fail in the case when input is
[{1,1,1,1},
{1,1,0,0},
{1,0,0,0},
{0,0,1,1}]
it would return row 4 instead of 3.

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

@ kiruba..
its given in the question all 1's in each row shud cum before 0's.
u r giving wrong input.

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

1. Find the first occurrence of 0 in the first row, let's say it's the kth element, if no 0s then k==n. This takes O(n)

2. From this element, we go down to the next row, if the kth element is 1, then we skip this row; else find the 'dividing element' in this row and we update k.

Observe that the number k will be strictly non-ascending, meaning that the updating happens for at most n-1 times, thus it gives a time complexity of O(n).

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

Worst case, that implementation is O(n^2) In the case where the first row is all 1s and the last row is all 0s. And each row in between adds a single 0 to each row.

n x (n-1) == n^2 not O(n)

An arguably better implementation would be to do a column wise search first.

Since you know all the ones appear first you should search all rows at position 0 for a 0, then all rows at position 1 for a 0, then all rows at position 2 for a 0, etc... until you find your first 0. Once you hit your first 0 the row you are marks the row with the fewest 1s (and therefore most 0s).

This has the same worst case implementation O(n^2) but that is only the case when there are no 0s (or the 0 is the last element). The average case would k*n where k is the number of 1s in the row with most 0s.

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

@Isaac: No, the original answer correctly shows that this algorithm is O(n). At most 2*n values are inspected by this algorithm.

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

@Chen your algo looks good.. but the first step can be achieved in log(n) time right (a binary search can be done)?
Then the algo would take O(log(n)) + O(n) instead of O(n) + O(n)..

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

Regardless, the total running time of the algorithm is O(n).

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

Here's a little approach I came up with using ArrayLists. I don't know if using Lists and Collections.frequency is any more or less efficient?

``````Byte[][] matrix = {
{1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};

List<Byte> list = new ArrayList<Byte>();

int r = 0,
c = matrix[r].length,
max = 0, location = 0;

while ( r < matrix.length && c > 0 )
{

list = Arrays.asList(matrix[r]);
Byte b = new Byte((byte) 0);

if ( Collections.frequency(list, b) > max)
{
max = Collections.frequency(list, b);
location = r;
}
r++;
c--;

}

System.out.println(location);``````

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

Well this question is trivial ,
it can be solved in O(n) time ..

here is my approach
Start from the top right element
if you heat 1 then go down
if you heat zero goto left
last location is your row with max zeros ..

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

it will not work for this case -

0-0-0-0
1-0-0-0
1-0-0-0
1-1-1-1

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

you go to top right corner ,
follow this, if your current value is zero then move to left,
if current value is 1 then move down..

in your example you keep moving to left till your pointer ends row length ..so it works dude

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

you go to top right corner ,
follow this, if your current value is zero then move to left,
if current value is 1 then move down..

in your example you keep moving to left till your pointer ends row length ..so it works dude

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

1-1-1-0
1-1-1-1
1-1-1-1
1-1-1-1

This will not work in this case

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

obviously we are keeping track of previous found row

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

Well, this question is trivial if u solve in O(n).
Try binary search on each row and you will perform better

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

Rather than simply scanning the first row, apply the binary search only on the 1st row and then follow the above method of going towards right each time you encounter a zero. If you encounter 1 move to the next row. If you reach column 0 then return.

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

Rather than simply scanning the first row, apply the binary search only on the 1st row and then follow the above method of going towards right each time you encounter a zero. If you encounter 1 move to the next row. If you reach column 0 then return.

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

We can achieve this in NlogN. here is the approach

2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.

Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0

Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes

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

why n lg n .. when you can do it in linear time ..

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

We can achieve this in NlogN. here is the approach

2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.

Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0

Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes

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

When ever there is a zero in the first column means rest are also 0.
Do linear search column wise i.e. from col1,col2 etc ... search for a 0 , Row containing first 0 will be the answer.

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

1. Find the first occurrence of 0 in the first row, let's say it's the kth element, if no 0s then k==n. This takes O(n)

2. From this element, we go down to the next row, if the kth element is 1, then we skip this row; else find the 'dividing element' in this row and we update k.

Observe that the number k will be strictly non-ascending, meaning that the updating happens for at most n-1 times, thus it gives a time complexity of O(n).

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

Here is my solution using Scala. Time complexity around N*logN.

``````def find(m:Array[Array[Int]]):Option[Array[Int]] = {
def _find(m:Array[Array[Int]], range:(Int, Int) ):Option[Array[Int]] = {
if (range._1 >= m.size) return None //out of the border
val median = if (range._1 == range._2)  {
range._1 //range reduced to one column
} else {
range._1 + ((range._2 - range._1) / 2) //find the range median
}

val rows:Array[Array[Int]] = m.filter {(row)=>row(median) == 0} //locate rows with '0' at median position
rows.size match {
case notFound if (notFound == 0) => _find(m, (median+1, range._2)) //try the right side
case one if (one == 1)=> Some(rows(0)) //found it!
case _ =>
if (median == 0) return Some(rows(0)) //first column
_find(m, (range._1, median-1)) //more to explore on the left side
}
}
_find(m, (0, m.size))
}``````

It also handles situation when no rows with zero's. And even when all of them are zeroes :)

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

We can search each column and which

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

We can scan each column and whichever row we would find zero that would have maximum zeros in it :
So for ex :
1 1 0
1 0 0
1 0 0
In this matrix we scan first column all are 1`s so nothing happened
Then again we scan through second column and we found zero in second and third row so we output these rows as having max. no. of 0`s

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

How about taking every row and right shifting it until we reach (row & 1) = 1 and having this count. If a new count exceeds the previous count , maintain the new count ..

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

One approach that I could think of is:
- Since all one comes before the zeros, sum up all all the values in a row until zero is found.
- Hold the row number of the lowest sum.
- The lowest sum row would be the one which contains maximum zeros

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

Set the first row as bestRow and find the bestColumn (corresponding to left most '0').
Iterate through rest of the rows
->If this row has a '0' in column bestColumn - 1, then set this row as bestRow and find the actual bestColumn of this row (corresponding to left most '0').
At the end of the loop, bestRow is the row that you are looking for and bestColumn contains the left most '0' in that row.

Complexity O(n)

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

#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#define COL 4
#define ROW 4
using namespace std;
int main()
{
int arr[ROW][COL]= {
{1,1,1,1},
{1,1,0,0},
{1,0,0,0},
{1,1,0,0},
};

int rownum;
int i = 0, j = COL;
while(i<ROW && j>=0)
{
if(arr[i][j]==0)
{
j--;
rownum=i;
}
else
i++;
}
printf("%d",rownum);
getch();
return 0;
}
correct one.....

Comment hidden because of low score. Click to expand.

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.