## Amazon Interview Question for Software Engineer / Developers

• 0

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

do a binary search on (0,0) and (m,m ) i.e. (5,5) , when diagonal search could not find the number and we end up with one diagonal position say (p,q), then we have to search that particular row (row q) (from 0 to p) and column (column q) for that number. we can use binary search here too

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

Say we have a mxn matrix. Pick the m/2 nd row. Find the median using the quick-select algo. Now this median is larger than all the elements in the top-left m/2xn/2 matrix and lesser than all the elements in the bottom-right m/2xn/2 matrix. So if the target is less than the median we dont have to look at the elements in the bottom-right and if the target is greater than the median we dont have to look at elements in the top left. Do this recursively on the smaller matrices we get till we find the target.I think the recurrence will come out to be some thing like T(n)=3T(mn/4)+m.any thoughts?

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

Assume columns are sorted ascending top to bottom and rows ascending left to right.

Start with bottom left element. If given element is greater, eliminate the column, else if lesser, eliminate the row.

Pick bottom left of resulting matrix.

O(m+n) time algo. This is a pretty standard problem and the solution is pretty standard too.

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

thanks...

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

Good solution :)

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

great solution

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

Or you could start from right top element

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

didn't you see chazzzzzz's solution? That's O(log(n))

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

chazzzzzz's solution looks like BS to me. What about it?

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

int findElement(Matrix M, int val)
{
int i,j;
for(i=0, j=n-1;i<m && j>=0;)
{
if(M[i][j]==val){
return 1;
else if(M[i][j]<val)
j--;
else if(M[i][j]>val)
i++;
}
return 0;
}

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

Arun,

I asssume you wanted to start from one corner and here u start from top right corner. If this was the case, I believe the following correction needs to be made in your code. Correct me if I am wrong.
...
...
if(M[i][j]>val)
j--;
else if(M[l][j]<val)
i++;
...
...

I am trying to point out mistake in the code and I understand that u have the correct logic.

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

{{
bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
if (i >= m || j >= n)
return false;
int x = (i + m) / 2,
y = (j + n) / 2;
int v = matrix[x][y];
if (v == key)
return true;
if (key > v)
return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
// key < v
return search(key, i, j, m, y) || search(key, i, j, x, n);
}
}}

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

``````bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
if (i >= m || j >= n)
return false;
int x = (i + m) / 2,
y = (j + n) / 2;
int v = matrix[x][y];
if (v == key)
return true;
if (key > v)
return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
// key < v
return search(key, i, j, m, y) || search(key, i, j, x, n);
}``````

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

LOler is correcct fully .
Read chazzzz solution .... suppose m*m matrix (haven't generalized as maybe wrong !!)
x = element to find
now compare with a[m/2][m] if x > this (case 1)remove all the rows <m/2 else remove all the rows >m/2 (case 2)

now accordingly case 1: compare with a[m][m/2]
case 2: compare with a[m/2]

Maybe now reduced to m/2*m/2 array ie t(m) = t(m/2) + o(1) !!!!

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

I like chaz's solution alongwith LOLer's approach. Both are correct in finding the element efficiently. Rest sucks!

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

Hey just curious if this will work.

Let the element to searched (say r) be compared with middle row's last element (A[M/2][N]). If r is greater, then we check in the bottom matrix A[M/2+1,0] to A[M,N], else we check in the top matrix A[o,o] to A[M/2,N].

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.