## Amazon Interview Question

Development Support Engineers Software Engineer / Developersint 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;

}

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.

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.

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);

}

}

}

printf("\nNot Found!");

}

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)!

I got to say you might be wrong.

suppose the target is 67,your algorithm won't work out.

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)

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

```
#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;
}
```

```
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;
}
```

Solution to this question is given some where in this forum.

- Anonymous October 13, 2008idea was to bst technique starting from leftmost-bottom cell of grid.