## Amazon Interview Question for Development Support Engineers Software Engineer / Developers

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

Solution to this question is given some where in this forum.
idea was to bst technique starting from leftmost-bottom cell of grid.

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

this can be done in O((no_rows + no_colums)-1) in worst case when the element which we are looking is in top - most row, and last column.

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

Can you explain how?

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

int search(int arr[5][5],int x, int y, int num)
{
int found=0;

while(x>=0 && y<5)
{
complexity++;
if( arr[x][y]==num)
{
found=1;
break;
}
else if(arr[x][y]>num)
{
x--;
}
else
{
y++;
}

}

return found;
}

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

int found = search(arr,4,0,num);

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

How abt this....

First check if the element is <> A[n,n/2]. If its greater then we conclude that its in the right half the matrix (all rows, but columns greater than n/2 ). Else in the left half. (how ?? )
Now, assume that the given element is in the greater half, then check at <> A[n/2, n]. (if in left then check at A[n/2,n/2] ) We get a partition on both the sides.

It looks like
T[n] = 2 + T[n/4]. Which may spew out (log n)^2 ( a little rusty there ).

Thing left out - way to figure how to write smart breakpts.

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

k, I was wrong in forming the recursive equation. But the final complexity looks fine to me.

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

Another way is to find the right row where the element can be found. Then search in that row if the element is present or not.

Say given Arr is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

First search on the last col to decode the right row. To decide the right row:
check if the arr element is < num( to be found) then check with the next row last element.
if Equal then found.
if Arr element > num, then this is the right row.

Then search the elements in that row. Use Binary search to search in a row. Then we can solve the prob in O(n) + O(logn) in the worst case.

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

You can use binary search to find the right row too. That would make time required O(lg n) + O(lg m). Neat!

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

A simple solution to this problem is in O(n). Consider the fact that the matrix is a square matrix NxN and all of its rows and column are sorted. All we need to do is move diagonally across the matrix and see if the element is smaller than S then we move further diagonally . When we see that "S" is smaller than one of the diagonal element then we check in that diagonal element's row and column to see if S exists.

void check(int **a, int n, int S){
int i=0;
while(i<n){
if(a[i][i] == S){
printf("\n found at %d , %d",i,i);
}
else if(a[i][i] < S)
i++;
else {
for(int j=0;j<i;j++){
if(a[i][j] == S)
printf("\n found at %d , %d",i,j);
else if(a[j][i] == S)
printf("\n found at %d , %d",j,i);
}
}
}
}

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

Should we use quick-selection algorithm to solve this problem ?

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

We have to traverse the diagonal till we find a diagonal element b bigger than S. This will mean that earlier diagonal element a is smaller than S. Thus S lies in the column below a or column above b.
For eg. in matrix:
23 45 67 89
24 56 89 99
35 66 92 98
36 47 93 100
...suppose S is 89. Now we move through diagonal 23,56,92,100. We can say 89 lies between 56 and 92. Thus it lies in column below 56 or above 92.
This is in O(n)!

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

I got to say you might be wrong.
suppose the target is 67,your algorithm won't work out.

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

His solution is almost right!

Traverse along the diagonal until you find the first number greater than what you are looking for! Now, look in that particular row and column for the number. Complexity O(n)

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

in the case:

1 2 3
10 12 17
15 18 19

If we are searching for the number 2, according to your algo, we need to start searching at the cols and rows of 15 .. where 2 does not exist

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

I can do this in log(n).

use binary search to try to find the target value T in the last column. If found, return. Otherwise, check last position of the pointer of the binary search and the row that includes T can be easily determined. Search in that row use binary search to find T.

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

how about Binary search on the diagonal...

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

can we do it like this:
we compare S with bottom left element and top right element:
if S<both compare S with the upper diagonal
if S>both compare S with lower diagonal
else look for S in the same diagonal
this should be in O(n).
what say ?

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

At any stage, the top-left(0,0) is the smallest no in the matrix and bottom-right(n,n) is the largest.

Compare X to check if it lies in this range of smallest-largest no. If Yes, reduce space to a n-1 * n-1 matrix and compare with its smallest and largest no.

Continue reducing the space until X falls out of the range.
So,
1st iteration = n*n matrix
2nd iteration = (n-1) * (n-1) matrix
3rd iteration = (n-2) * (n-2) matrix and so on.

This would be O(n).

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

this question has been answered hell of times in this forum and as I remember the best and smartest answer was from LOLer with the complexity of O(rowCount+ colCount-1) as already mentioned by "Anonymous on October 14, 2008"

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

``````#include <iostream>

using namespace std;
/*
* type 1 : 1 2 3  4 5 6  7 8 9
* type 2 : 1 5 10 2 6 11 3 7 12
*/
int search(int a[][3], int e) {
int left = 0;
int n = 3;
int right = n * n - 1;
int mid = 0;
int val = 0;
bool is_type1 = false;
for (int i = 0; i < n - 1; i++) {
if (a[i][i + 1] == a[i + 1][i]) {
continue;
}
is_type1 =  (a[i][i + 1] < a[i + 1][i]);
}

while (left <= right) {
mid = (left + right) / 2;
if (is_type1) {
val = a[mid / n][mid % n];
} else {
val = a[mid % n][mid / n];
}

if (val == e) {
return true;
} else if (val < e) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}

int main() {
//int a[][3] = { {1, 5, 10}, {2, 6, 11}, {3, 7, 12} };
//int a[][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
//int a[][3] = { {1, 5, 10}, {5, 11, 12}, {10 , 13, 14} };
int a[][3] = { {1, 5, 10}, {5, 11, 12}, {10, 12, 13} };

for (int i = -1; i < 15; i++) {
if (search(a, i)) {
cout << i << endl;
}
}
return 0;
}``````

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

``````having some problems posting. ignore this if u have the proper version.
sorry for the confusion.

bool search(int a[][5], int n, int e) {
int left = 0;
int right = n * n - 1;
int mid = 0;
int val = 0;

while (left <= right) {
mid = (left + right) / 2;
val = a[mid / n][mid % n];
if (val == e) {
return true;
} else if (val < e) {
left = mid + 1;
} else {
right = mid - 1;
}
}

left = 0;
right = n * n - 1;
while (left <= right) {
mid = (left + right) / 2;
val = a[mid % n][mid / n];
if (val == e) {
return true;
} else if (val < e) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}``````

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.