## Amazon Interview Question for SDE-2s

Country: India
Interview Type: Phone Interview

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

``````public static bool SearchIn2D(int[,] arr, int target)
{
int size = arr.GetLength(0);
int i = 0, j = size - 1;
for (; i < size && j < size && i >= 0 && j >= 0;)
{
if (arr[i, j] == target)
return true;
if (arr[i, j] > target)
j--;
else
i++;
}
return false;
}``````

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

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] == a)
return 1;

if(mat[rm] > 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.length;

if(r == 0 || c == 0)
return -1;

return rec(mat, a, 0, r - 1, 0, c - 1);
}``````

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

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.

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

/*
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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Recursive C# code for this question.

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

}``````

Comment hidden because of low score. Click to expand.

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.