NetApp Interview Question
Software Engineer / Developers<pre lang="java" line="1" title="CodeMonkey63692" class="run-this">public class Saddleback {
public static String saddleback_search(int matrix[][], int elem)
{
int h = 0;
int k = matrix[0].length-1;
int rowCount = matrix.length-1;
while (matrix[h][k]!=elem && h<rowCount && k>0)
{
if (matrix[h][k]<elem)
h++;
if (matrix[h][k]>elem)
k--;
if (matrix[h][k]== elem)
return Integer.toString(h)+","+Integer.toString(k);
}
return "NOT FOUND";
}
public static void main(String args[])
{
int matrix[][]=new int[4][4];
matrix[0][0]=2;
matrix[0][1]=2;
matrix[0][2]=3;
matrix[0][3]=5;
matrix[1][0]=3;
matrix[1][1]=4;
matrix[1][2]=5;
matrix[1][3]=6;
matrix[2][0]=3;
matrix[2][1]=5;
matrix[2][2]=6;
matrix[2][3]=8;
matrix[3][0]=3;
matrix[3][1]=6;
matrix[3][2]=7;
matrix[3][3]=9;
System.out.println(Saddleback.saddleback_search(matrix, 9));
}
}
</pre><pre title="CodeMonkey63692" input="yes">This Java code should work.</pre>
If sorting is done in increasing order: start with the top rightmost element and if current-value < element to search, move down, and if current-value> element to search move left. Continue this till one of the index values become negative(that is you have moved out of the array).
Similar approach will be used for decreasingly sorted array.
lets the array
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
start from top right element i.e.. 5, if the target number is greater than a[5,5] then search with a[1,5] else a[0,4] continue this one till find the number
lets the array
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
start from top right element i.e.. 5, if the target number is greater than a[5,5] then search with a[1,5] else a[0,4] continue this one till find the number
Since the matrix is sorted so is the submatrices.
- jayeshr007 December 05, 20121. compare key with A[m/2][n/2]
2. if key > A[m/2][n/2] , then search in the lower right submatrix
3. if key < A[m/2][n/2] , then search in the upper left submatrix
4. else if (key == A[m/2][n/2]) ret TRUE
5. else ret FALSE
recursively follow this
This gives a O(log(MN)) solution which is better than O(m)
Correct me if i am wrong