Amazon Interview Question
SDE-2sTeam: Hyderabad
Country: India
Interview Type: Phone Interview
Run Binary Search on first column until one row is left and then run Binary Search on that one row O(logr + logc) {r : number of rows, c : number of columns}
static private int BinarySearch(int[][] mat, int a, int rs, int cs, int ce){
if(cs > ce)
return -1;
int[] arr = mat[rs];
int mid = cs + (ce - cs)/2;
if(arr[mid] == a)
return 1;
if(arr[mid] > a)
return BinarySearch(mat, a, rs, cs, mid - 1);
else
return BinarySearch(mat, a, rs, mid + 1, ce);
}
static private int rec(int[][] mat, int a, int rs, int re, int cs, int ce){
if(rs > re)
return -1;
if(re - rs == 0)
return BinarySearch(mat, a, rs, cs, ce);
int rm = rs + (re - rs)/2 + 1;
if(mat[rm][0] == a)
return 1;
if(mat[rm][0] > a)
return rec(mat, a, rs, rm - 1, cs, ce);
else
return rec(mat, a, rm, re, cs, ce);
}
static public int bs2d(int[][] mat, int a){
int r = mat.length;
int c = mat[0].length;
if(r == 0 || c == 0)
return -1;
return rec(mat, a, 0, r - 1, 0, c - 1);
}
There are two approaches possible: The first one is: Perform a binary search vertically (Which takes O ( N )) and then perform a binary search inside the row found (which takes O (M)). Since O (N) + O(M) takes O (N*M) then we can say that it's like performing a binary search over a huge array that is composed of segments made of rows. So that
BigArray[i] = matrix[i / M, i % M]. So it's simpler to peform a binary search over the BigArray.
/*
0-> x x x x x->4
x x x x x
x x x x x 15 -> (3,0) m=x/5 n=x%5
x x x x x->19
*/
class Search{
public static void main(String[] args){
Search s=new Search();
int[] a={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
int x=15;
s.find(x,4,5,a);
}//end of main
void find(int x,int m,int n,int[] a){
int start=0;
int end=n*m-1;
binarySearchC(x,a,start,end);
return;
}//end of find
void binarySearchC(int x,int[] a,int s,int e){
if(s<e){
int m=(s+e)/2;
if(x==a[m]){
System.out.println(m/5+" , "+m%5);
return;
}else if (x<a[m]){
binarySearchC(x,a,s,m);
}else{
binarySearchC(x,a,m,e);
}//end of else
}//end of if
}//end of binarySearch
}//end of class
Recursive C# code for this question.
Explanation on comments in-line.
static bool Search(int num, int[,]matrix,int m,int n) //m: number of rows, n: number of columns
{
if (num < matrix[0, 0] || num > matrix[m - 1, n - 1]) return false;
return SearchUtil(num, matrix,0, m, 0, n);
}
static bool SearchUtil(int num, int[,]matrix,int minI,int maxI, int minJ,int maxJ)
{
while (minI<=maxI)
{
int midI = (minI + maxI) / 2;
int midJ = (minJ + maxJ) / 2;
if (matrix[midI, midJ] == num)
return true;
if (num > matrix[midI, midJ]) //If the number is greater than the middle element, it's either on the same row on middle's right side, or the next rows anywere.
{
if (num <= matrix[midI, maxJ - 1]) //if it's smaller or equal to the largest element in this row;
{
return SearchUtil(num, matrix, midI, midI, midJ, maxJ); //it's on the same row, to the right of the middle element.
}
else //if it's bigger than the middle element;
{
return SearchUtil(num, matrix, midI + 1, maxI, 0, maxJ); //it's for sure on one of the next rows.
}
}
if (num < matrix[midI, midJ]) //If the number is smaller than the middle element, it's either on the same row on middle's left side, or the previous rows anywere.
{
if (num >= matrix[midI, 0]) //if it's greater or equal to the smallest element in this row;
{
return SearchUtil(num, matrix, midI, midI, 0, midJ); //it's on the same row, to the left of the middle element.
}
else
{
return SearchUtil(num, matrix, 0, midI - 1, 0, maxJ); //it's for sure on one of the previous rows.
}
}
}
return false;
}
- apt4790 January 31, 2017