Amazon Interview Question for Software Engineer / Developers


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;

}

- nihaldps February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution...

- Sunny_Boy February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution...

- Sunny_Boy February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- andy February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Orchid Majumder March 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Orchid Majumder March 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- nihaldps March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Goldenmean March 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vinit March 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

simple and nice solution!

- lippie_ March 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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.

- Kiruba March 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- heena August 11, 2012 | Flag
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).

- Chen Xie February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Isaac March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SecretAgent March 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 12, 2012 | Flag
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);

- t-rev March 05, 2012 | Flag Reply
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 ..

- yogeshhan February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not work for this case -

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

- codemaniac February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yogeshhan February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yogeshhan February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about this case
1-1-1-0
1-1-1-1
1-1-1-1
1-1-1-1

This will not work in this case

- sk February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

obviously we are keeping track of previous found row

- yogeshhan February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- andy February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vijay March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vijay March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can achieve this in NlogN. here is the approach

1. Start with the middlle column and look for any zeros
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

- loveCoding February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yogeshhan February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can achieve this in NlogN. here is the approach

1. Start with the middlle column and look for any zeros
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

- loveCoding February 29, 2012 | Flag Reply
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.

- Tushar February 29, 2012 | Flag Reply
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).

- Chen Xie February 29, 2012 | Flag Reply
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 :)

- IvanoBulo February 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can search each column and which

- Chinmay March 09, 2012 | Flag Reply
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

- Chinmay March 09, 2012 | Flag Reply
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 ..

- Dam March 13, 2012 | Flag Reply
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

- jainsaurabh86 March 17, 2012 | Flag Reply
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)

- Anonymous May 08, 2012 | Flag Reply
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.....

- Anonymous August 30, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.


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