## Amazon Goldman Sachs Interview Question for Software Engineer / Developers Applications Developers

• 0

Country: India
Interview Type: In-Person

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

``````Start with top right element
Loop:
Compare this element e with x
i) if they are equal then return its position
ii) e < x then move it to down
iii) e > x then move it to left
Repeat above 3 steps till you find element

Make a check at each step that the index is not out of bound.
Time Complexity: O(n)
Space Complexity: O(1)

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

@Expressions you can start even from bottom left and get the same results.

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

Exactly!

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

The code in Java is as follows:

``````boolean search_element(int a[][],int key)
{
int m=a.length;
int n=a[0].length;
int k=0;
while((k<m) && (n>=0))
{
if(key<a[k][n-1])
n--;
else if(key>a[k][n-1])
k++;
else if(key==a[k][n-1])
return true;
}
return false;
}``````

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

Given input x, using binary search find the largest first element which is smaller than input.
Then use binary search in row to see if there is an element that matches x.

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

Move to the top right cell, ie the last column in first row. Then keep moving to left or down by comparing the element at that cell with the one to be searched.
e.g.
1 2 3 4
4 5 6 8
6 8 9 10

Suppose we are searching for 7. Starting from 4, since 7>4, we move down to 8 then 6 then 9 then 8 and finally end on 6 (which is on the bottom left cell), and hence 7 doesn't exist.

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

can u write the code plss???

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

boolean search(int[][] a, int value){
int maxx=a[0].length;
for(int j=0; i<a.length;i++){
for(int i=maxx;i>=0;i--){
if(a[i][j]==value) return true;
if(a[i][j]<value) break;
maxx=i;
}
}
return false;
}

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

@kobe:i can't understand ur code.Can u pls elaborate a bit.
And I think in place of a[i][j],it will be a[j][i].

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

@mng

You are right. we start from top right element, but we can do binary search thereafter, instead of going through each element.

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

bool search2D(int ele, int **mat, unsigned row, unsigned col, unsigned &oRow, unsigned &oCol)
{
unsigned i = 0;
unsigned j = row;

if ((ele > mat[row][col]) || (ele < mat[0][0]))
{
return false;
}

while (i<j)
{
unsigned k = (i+j)/2;
if (mat[k][col] > ele)
{
j = k;
}
else if (mat[k][col] < ele)
{
i = k+1;
}
else
{
oRow = k;
oCol = col;
return true;
}
}

oRow = i;

if (mat[oRow][col] == ele)
{
oCol = col;
return true;
}

for (i=0,j=col; i<j;)
{
unsigned k = (i+j)/2;
if (mat[oRow][k] > ele)
{
j = k;
}
else if (mat[oRow][k] < ele)
{
i = k+1;
}
else
{
oCol = k;
return true;
}
}

if (mat[oRow][i] == ele)
{
oCol = i;
return true;
}

return false;
}

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

mng soln seems to be appropriate

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

An approach with O(m log n) complexity would be to perform binary search on every row... Can we do better than this?

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

``````class point
{
public int X {set; get; }
public int Y {set; get; }
public point(int x, int y)
{
this.X = x;
this.Y = y;
}
}
class Searching
{
public static point SearchIn2DSortedArray(int[,] arr, int Key)
{
int MaxX = arr.GetLength(1) - 1;
int MaxY = arr.GetLength(0) - 1;

if (MaxY < 1 || MaxX < 1)
goto RETURN_KEY_NOT_FOUND;
if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
goto RETURN_KEY_NOT_FOUND;

int X = MaxX;
int Y = 0;

while (X >= 0 && Y <= MaxY)
{
if (Key == arr[Y, X])
return new point(Y, X);

if(Key < arr[Y, X])
{
X--;
continue;
}

if(Key > arr[Y, X])
{
Y++;
continue;
}
}
RETURN_KEY_NOT_FOUND:
return new point(-1, -1);
}
}``````

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

``````class point
{
public int X {set; get; }
public int Y {set; get; }
public point(int x, int y)
{
this.X = x;
this.Y = y;
}
}
class Searching
{
public static point SearchIn2DSortedArray(int[,] arr, int Key)
{
int MaxX = arr.GetLength(1) - 1;
int MaxY = arr.GetLength(0) - 1;

if (MaxY < 1 || MaxX < 1)
goto RETURN_KEY_NOT_FOUND;
if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
goto RETURN_KEY_NOT_FOUND;

int X = MaxX;
int Y = 0;

while (X >= 0 && Y <= MaxY)
{
if (Key == arr[Y, X])
return new point(Y, X);

if(Key < arr[Y, X])
{
X--;
continue;
}

if(Key > arr[Y, X])
{
Y++;
continue;
}
}
RETURN_KEY_NOT_FOUND:
return new point(-1, -1);
}
}``````

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

``````class point
{
public int X {set; get; }
public int Y {set; get; }
public point(int x, int y)
{
this.X = x;
this.Y = y;
}
}
class Searching
{
public static point SearchIn2DSortedArray(int[,] arr, int Key)
{
int MaxX = arr.GetLength(1) - 1;
int MaxY = arr.GetLength(0) - 1;

if (MaxY < 1 || MaxX < 1)
goto RETURN_KEY_NOT_FOUND;
if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
goto RETURN_KEY_NOT_FOUND;

int X = MaxX;
int Y = 0;

while (X >= 0 && Y <= MaxY)
{
if (Key == arr[Y, X])
return new point(Y, X);

if(Key < arr[Y, X])
{
X--;
continue;
}

if(Key > arr[Y, X])
{
Y++;
continue;
}
}
RETURN_KEY_NOT_FOUND:
return new point(-1, -1);
}
}``````

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

Suppose we have 2D matrix with bottom left corner as starting point. Now compare the last element of first column and last row with the matching element. If the last elements are smaller then move to next diagonal element and repeat the above steps. If last element is bigger then we are sure that matching element should be present in current row or column so do binary search to find it.

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

A simple algo can be as below:
1) Given Matrix[i][j] where i and j are the rows and columns of the table.
2) If entered number, E is less than M[0][0] or greater than M[n][n] then print element does not present in matrix.
3) Check element start from first row and then subsequent rows .... E < = M[0][3]
then start for 1st row to check whether E=M[0][j] for j = 0,1,2,3
4) Return if you find suitable match or return "Element is not present in the given matrix"
5) End

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

Take a point at n/sqrt(2),m/sirt(2). Compare with key. If you find key bigger then this, that means key is in lower right rectangle. Space of this rectangle is n*m/2. If key is lower, key could be above this element or on left of it. Any way we split all array on 2 parts of about half space. Use same technic to split area left by half. At some moment area left wold be something like two intervals or one interval of single element. Any way it is trivial to use bsearch on it.
complexity O(log(N*M)) and O(1) space.

Cheers

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.