Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
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)
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..
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..
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.
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},
}
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.
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).
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: No, the original answer correctly shows that this algorithm is O(n). At most 2*n values are inspected by this algorithm.
@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)..
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);
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 ..
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
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
Well, this question is trivial if u solve in O(n).
Try binary search on each row and you will perform better
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.
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
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
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).
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 :)
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
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)
#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.....
Here is a working code in C. The complexity is of O(n).
}
- nihaldps February 29, 2012