CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-3s


Country: United States
Interview Type: In-Person
More Questions from This Interview



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

- Chris August 31, 2017 | Flag Reply
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)
            {
                // already visited
                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));
     }

- Anonymous August 31, 2017 | Flag Reply
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)
            {
                // already visited
                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));
      }

- pranaypratap August 31, 2017 | Flag Reply
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]);
}

- Misgana September 01, 2017 | Flag Reply
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]);
}

- misgana.bayetta September 01, 2017 | Flag Reply
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;
	}
}

- Anonymous September 02, 2017 | Flag Reply


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