Amazon Interview Question Software Engineer / Developers
In my opinion the solution should go like this:
Search rowise first:
start looking for element in Row=0 and as soon as you find two columns, one which is less than your SEARCH number and one which has higher than your SEARCH number. So we can look for our number in these 3 columns, which is worst case would give us a running time of 3N i.e. O(N).
Please correct me if I am wrong or if you have any other interesting solution.
I think we should search the diagonal of the matrix which is sorted, then search the row and column.
Since every row/col/diagonal is sorted, we can even use binary search to get a O(logn)
This is a tricky one. i myself spent
ample time looking for linear time.
the answer is pretty simple. start
with top right element and do this :
1 compare the element(e) with query element(q)
2 if they are equal bingo, return (FOUND)
3 else
if e > q
move pointer to left if u can, else return
as UNFOUND
else
move pointer to down if u can, else return
as UNFOUND
- now repeat from step1
in step 3, you always ignore one row or column,
so it runs in O(row_count + col_count). it
converges as you will eventually an edge and cannot move further. remember we will only move
down or left.
1 11
10 12
i am finding 11 ...
so e = 1 and q = 11...
according to the algorithm i will never find 11 ... would I?
My approach would be to divide the matrix.
problem:
10 11 12 13
14 15 16 17
18 19 20 21
22 23 24 25
Find 19....
we know that the element at the right most bottom is the largest element. compare element_query() with this element. if geater then no found else
compare with the next diagonal element 20. 19 < 20 . we can assume that element falls on the left of the diagonal. fine... compare the query element with the next diag element. 19>15 so element can be on the right on on the next row. element cannot be on the right of the diag as we found out. hence search the row corresponding to 20 to find 19. If present return true else element not found.
search(int row, int column, int value)
{
if( 0<= row < n && 0<= column<n)
{
if(array[row][column] > value)
search(row, column-1, value);
else if(array[row][column] < value)
search(row-1, column, value);
else
return true;
}
else
return false;
the very first time call is search(n,0,value)
2 Functions I have:
int doBinSearchOnRow(int row, int tillCol, int num); //returns index of match or the index of the closest number < num.
int doBinSearchONCol(int col, int tillRow, int num);
Solution:
int c = doBinSearchOnRow(1,n,num);
if a[1,c]== num return true;;
int r = doBinSearchONCol(1,n,num);
if a[r,1] == num return true;
int i = doBinSearchOnCol(c,r);
if(a[i,c] == num) return true;
i = doBinSearchOnRow(r,c);
if(a[r,i] == num) return true;
return false;
I found the following solution from some other site:
- madankumarrajan April 13, 2008Let X be the bottom left element of the matrix and we need to find the position of an element K.
Now if K = X, we can return the position of X.
Else if K < X, then we can possibly eliminate that row as all the elements in that row are greater than or equal to X.
Else if X < K, then we can eliminate that column as all the elements in that column are lesser than X.
Now in each step, we eliminate either a row or coll which finally leads to that element.