## Amazon Interview Question for Interns

Country: India
Interview Type: Phone Interview

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

Assuming both sorted in strictly increasing order:

``M[row][column] < M[row+1][column] and M[row][column] < M[row][column+1]``

Start from the top-right corner of the matrix. If the matrix element is larger than the target, move to the column on the left; if smaller, move to the row below.

Complexity if O(#rows + #columns)

``````public Position searchSortedMatrix(int x, int[][] M) {
if (M.length==0 || M.length==0) return Position(-1,-1);
int row = 0, column = M.length-1, curVal;
while (row<M.length && column>=0) {
curVal = M[row][column];
if (curVal == x) return Position(row,column);
if (curVal > x) column--;
else row++;
}
return Position(-1,-1);
}``````

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

can't we do a binary search across rows and column? start at the middle row and move up and down till we narrow down the row and then the same thing on the columns. O(log rows * log cols )

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

Binary search won't work in this problem.

The catch is that there the target value can be in the range of multiple rows or columns.

Take the example with looking for x=12 in the following matrix:

``````1, 2, 3, 4, 5
6, 10, 20, 30, 40
7, 11, 21, 31, 41
8, 12, 22, 32, 42
9, 13, 23, 33, 43``````

You have 4 rows and 4 columns that can potentially contain 12. Which row and column should you continue the iteration in binary search?

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

I think combination of recursion and binary search can solve this problem easily with O(log rows * log cols ) complexity.

In above case we will start with middle as it is the median of medians in the matrix, so the bottom-right part will be greater than the middle number and top left will be smaller than the middle number. In this way we can eliminate searching 1/4 of the matrix. If we continue doing it recursively with logically changing the matrix sizes and searching them recursively.
In the end we will be left with one row at the bottom of the tree where we need to do the binary search to determine the element.
I will try to code it and see if this works. Please let me know if you there is any problem with this approach .

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

@id
This got me thinking. This may not be very efficient solution because the recurrence relation 'you think' you have here is T(n) = 4T(N/4) + c (where N = n^2) ~ leading to log<base 4>(n^2) complexity. But it's NOT.
Unlike binary search, this does not result in a decision tree at all, since after dividing in four parts, you may not be able to pinpoint one of the parts to proceed and may end up searching each 1/4 from every decision.
Which means that worst time-complexity, my friend, is 4(n^2/4) ~ n^2 (leaving this as an exercise). Let me know if you need anymore clarification.

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

@Roxanna Ya that's true. I realized it while implementing it. Thanks for clarification anyway. So the efficient algorithm would be the one which gives O(nrows+ncols), to follow a path and move right or down according to the value? or is there any other better solution

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

We can check the diagonal elements and eliminate whole squares and continue it

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

sorted in row+column means you can just "flat out" the matrix into an array to do a binary search.

turn:
1 3 4 5
6 6 7 7
9 9 10 10
12 17 29 31

into:
1 3 4 5 6 6 7 7 9 9 10 10 12 17 29 31

we don't need to "physically" rearrange the matrix into an array by coping or something.

As@chriscow made a good point that the biggest problem with binary search is that we don't know what row/column to continue for the iteration. We can work on that:

``````int nRow = matrix.length;
int nCol = matrix.length;

public static int getElementByIdx(int flatMatrixIdx, int[][] matrix, int nRow, int nCol){
int n = nRow * nCol;
if (flatMatrixIdx > n) {
throw new Execption("index out of range");
}
int xRow = idx / nCol;
int xCol = idx - nCol * xRow;
return matrix[xRow][xCol];
}

// do a binary search here
public static void binarySearchOnSortedMatrix(int[][] matrix, int target) {
// blah
}``````

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

time complexity will still be O(nRow + nCol), it's just cleaner to understand the process. Actually Matlab provides same method as this to traverse a matrix.

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

I don't think your understanding about sorted row+column is correct. The following matrix is sorted row+column, but you can't flatten it.

``````1  2  4  7
3  5  8  11
6  9  12 14
10 13 15 16``````

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

thanks, I missed that...

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.