Amazon Goldman Sachs Interview Question
Software Engineer / Developers Applications DevelopersCountry: India
Interview Type: In-Person
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.
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.
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;
}
@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].
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;
}
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);
}
}
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);
}
}
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);
}
}
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.
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
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
Make a check at each step that the index is not out of bound.
- Expressions April 09, 2013Time Complexity: O(n)
Space Complexity: O(1)