Amazon Interview Question for SDE-2s


Team: Hyderabad
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;
        }

- apt4790 January 31, 2017 | Flag Reply
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][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);
	  }

- amaniitm.gupta26 January 20, 2017 | Flag Reply
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.

- aurelian.lica January 26, 2017 | Flag Reply
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

- Farzam Ghanbarnezhad February 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- yasharonline January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More