## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: In-Person

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

straight forward DP solution with O(n*m) space and time complexity.

the recursion is

``````max_rect(i, j) = min(max_rect(i-1, j), max_rect(i, j-1), max_rect(i-1, j-1)) if i > 0 and j > 0
0 if i < 0 or j < 0``````

``````#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

void findMaxSquare(const vector<vector<int>>& matrix)
{
int m = matrix.size();
int n = m > 0 ? matrix[0].size() : 0;
vector<vector<int>> dp(vector<vector<int>>(m+1, vector<int>(n+1, 0)));
int max_sq = 0;
int max_i = -1;
int max_j = -1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
int cur = min(dp[i][j], min(dp[i][j + 1], dp[i + 1][j])) + 1;
dp[i + 1][j + 1] = cur;
if (cur > max_sq) {
max_sq = cur;
max_i = i - cur + 1; // from top
max_j = j - cur + 1; // from left
}
}
}
}
cout << "edge length: " << max_sq << ", from top: " << max_i << ", from left: " << max_j;
}

int main()
{
findMaxSquare(
{
{1,0,0,1,0,0},
{1,0,1,1,1,1},
{0,1,1,1,1,0},
{1,1,1,1,1,0},
{1,0,1,1,1,0},
}
);
}``````

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

``````public static int FindMaxSubSquareMatrix(int[,] arr)
{
if (null == arr)
{
throw new ArgumentNullException();
}

if (arr.GetLength(0) == 0 || arr.GetLength(1) == 0)
{
return -1;
}

int[,] map = new int[arr.GetLength(0), arr.GetLength(1)];
for (int i =0; i<map.GetLength(0); i++)
{
for (int j =0; j<map.GetLength(1); j++)
{
map[i,j] = -1;
}
}
DoFindMaxSubSquareMatrix(arr, 0, 0, map);
int max = 0;
for (int i = 0; i < map.GetLength(0); i++)
{
for (int j = 0; j < map.GetLength(1); j++)
{
if (map[i,j] > max)
{
max = map[i,j];
}
}
}

return max;
}

private static int DoFindMaxSubSquareMatrix(int[,] arr, int i, int j, int[,] map)
{
if (i >= arr.GetLength(0) || j >= arr.GetLength(1))
{
// out of bounds
return 0;
}

if (map[i,j] != -1)
{
return map[i,j];
}

int right = DoFindMaxSubSquareMatrix(arr, i + 1, j, map);
int down = DoFindMaxSubSquareMatrix(arr, i, j + 1, map);
int diagonalDown = DoFindMaxSubSquareMatrix(arr, i + 1, j + 1, map);
int subSquareSize = right == down && right == diagonalDown ? right : Math.Min(right, Math.Min(down, diagonalDown));
int result = arr[i, j] == 1 ? 1 + subSquareSize : subSquareSize;
map[i, j] = result;
return result;
}

static void Main(string[] args)
{
int[,] matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 1, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 5]
{
{ 1, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
}``````

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

``````public static int FindMaxSubSquareMatrix(int[,] arr)
{
if (null == arr)
{
throw new ArgumentNullException();
}

if (arr.GetLength(0) == 0 || arr.GetLength(1) == 0)
{
return -1;
}

int[,] map = new int[arr.GetLength(0), arr.GetLength(1)];
for (int i =0; i<map.GetLength(0); i++)
{
for (int j =0; j<map.GetLength(1); j++)
{
map[i,j] = -1;
}
}
DoFindMaxSubSquareMatrix(arr, 0, 0, map);
int max = 0;
for (int i = 0; i < map.GetLength(0); i++)
{
for (int j = 0; j < map.GetLength(1); j++)
{
if (map[i,j] > max)
{
max = map[i,j];
}
}
}

return max;
}

private static int DoFindMaxSubSquareMatrix(int[,] arr, int i, int j, int[,] map)
{
if (i >= arr.GetLength(0) || j >= arr.GetLength(1))
{
// out of bounds
return 0;
}

if (map[i,j] != -1)
{
return map[i,j];
}

int right = DoFindMaxSubSquareMatrix(arr, i + 1, j, map);
int down = DoFindMaxSubSquareMatrix(arr, i, j + 1, map);
int diagonalDown = DoFindMaxSubSquareMatrix(arr, i + 1, j + 1, map);
int subSquareSize = right == down && right == diagonalDown ? right : Math.Min(right, Math.Min(down, diagonalDown));
int result = arr[i, j] == 1 ? 1 + subSquareSize : subSquareSize;
map[i, j] = result;
return result;
}

static void Main(string[] args)
{
int[,] matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 1, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 0 },
{ 0, 0, 1, 0 },
{ 1, 0, 0, 0 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 4]
{
{ 1, 1, 0, 0 },
{ 0, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
matrix14931 = new int[4, 5]
{
{ 1, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 }
};
Console.WriteLine(ArrayQuestions.FindMaxSubSquareMatrix(matrix14931));
}``````

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

/*
* Given a binary matrix, find the largest subsquare matrix.
*
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;
int* getLargest(uint col, int row, uint M[][col])
{
static int r[3] = { 0, 0, -1 };

for (uint j = 0; j < row; j++) {
for (uint i = 0; i < col; i++) {
uint clen = 1, minrlen = UINT_MAX;
int sz;

if (M[j][i] == 1) {
for (uint l = i + 1; l < col; l++) {

if (M[j][l] != 1)
break;

++clen;

uint rlen = 1;
for (uint m = j + 1; m < row; m++) {
if (M[m][l] != 1)
break;
++rlen;
}

if (rlen < minrlen)
minrlen = rlen;
}
}

if (clen < minrlen)
sz = (int)clen;
else
sz = (int)minrlen;

if (sz > r[2]) {
r[2] = sz;
r[0] = j;
r[1] = i;
}
}
}

return r;
}

int main(int argc, char** argv)
{
uint row, col;
scanf("%u", &row);
printf("Row %u \n", row);
scanf("%u", &col);

printf("Col %u\n", col);
uint arr[row][col];
for (uint i = 0; i < row; i++) {
for (uint j = 0; j < col; j++) {
scanf("%u", &arr[i][j]);
//printf("Arr[%d][%d]=%d",i,j,arr[i][j]);
printf("%d ", arr[i][j]);
}
printf("\n");
}
printf("Array size %u,%u\n", row, col);
int* r = getLargest(col, row, arr);

printf("Largest subsquare with Ones @ %u,%u with Size %u \n", r[0], r[1], r[2]);
}

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

/*
* Given a binary matrix, find the largest subsquare
matrix.
*
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;
int* getLargest(uint col, int row, uint M[][col])
{
static int r[3] = { 0, 0, -1 };

for (uint j = 0; j < row; j++) {
for (uint i = 0; i < col; i++) {
uint clen = 1, minrlen = UINT_MAX;
int sz;

if (M[j][i] == 1) {
for (uint l = i + 1; l < col; l++) {

if (M[j][l] != 1)
break;

++clen;

uint rlen = 1;
for (uint m = j + 1; m < row; m++) {
if (M[m][l] != 1)
break;
++rlen;
}

if (rlen < minrlen)
minrlen = rlen;
}
}

if (clen < minrlen)
sz = (int)clen;
else
sz = (int)minrlen;

if (sz > r[2]) {
r[2] = sz;
r[0] = j;
r[1] = i;
}
}
}

return r;
}

int main(int argc, char** argv)
{
uint row, col;
scanf("%u", &row);
printf("Row %u \n", row);
scanf("%u", &col);

printf("Col %u\n", col);
uint arr[row][col];
for (uint i = 0; i < row; i++) {
for (uint j = 0; j < col; j++) {
scanf("%u", &arr[i][j]);
//printf("Arr[%d][%d]=%d",i,j,arr[i][j]);
printf("%d ", arr[i][j]);
}
printf("\n");
}
printf("Array size %u,%u\n", row, col);
int* r = getLargest(col, row, arr);

printf("Largest subsquare with Ones @ %u,%u with Size %u \n", r[0], r[1], r[2]);
}

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

It could be done in O(mxn) reading the matrix elements and with O(n) space (or O(min(m, n)) if we do the traversing in the lower dimension).

In this example the parsing is done line by line.
Each row we count the number of consecutive 1's above each column.
Each row we try to find a bigger square (start with 1x1, 2x2, ...)
We can only find NxN square if the previous line has at least N-1xN-1 square

``````public class MaxMatSquare {

// return value
private static class Square {
int top;
int left;
int size;
}

public static void main(String[] args) {
int[][] mat =
{
{0,1,1,0,0,0},
{1,0,1,1,0,0},
{1,1,0,1,0,0},
{1,0,1,1,1,1},
{0,0,0,0,1,1},
};
Square s2 = findMaxSquare2(mat);
System.out.println("top: " + s2.top + " left: " + s2.left + " size:" + s2.size);

}

public static Square findMaxSquare2(int[][] mat) {
int m = mat.length;
int n = m > 0 ? mat[0].length : 0;
int[] counters = new int[n];  // This count the number of consecutive rows with 1 in each col
// If there's on in the cur row in mat, increase the counter, otherwise zero it

int maxS = 0;  // Every row try to search for a square with bigger size than the last found one
// to serach for a square of size N there should be N consecutive counts each with >= N counts
// size N square can only exist if N-1 square was found before, therefore it's increased one by one
int tryS, tryCons;
Square s = new Square();

for (int i=0; i<m; i++) {
tryS = maxS+1;
tryCons = 0;
for (int j=0; j<n; j++) {
if (mat[i][j] == 1) counters[j]++;
else counters[j]=0;
if (counters[j]>=tryS) tryCons++;
else tryCons = 0;  // Try again
if (tryCons == tryS) {  // Square found
maxS = tryS;
s.size = tryS;
s.left = j-tryS+1;
s.top = i-tryS+1;
}
}
}
return s;
}
}``````

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.