## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

Program want diff b/w max and min value off matrix with given constraint (c>a and d>b). select randomly min and max in matrix such that c>a and d >b. In a loop find min and max in matrix with conditions and output difference,

let min=a,max[n-1][n-1] and a=0,b=0,c=n-1,d=n-1

for(i=0;i<n;i++)
{ for (j=0;j<n;j++)
{ if(min > a[i][j] && i<c && j <d)
{min=a[i][j];a=i;b=j;}
else if(max<a[i][j] && i>a && j>b)
{max=a[i][j];c=i;d=j;}
}
}

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

Step 1: first go over row by row, finding the max and min both. put them into separate arrays, would take O(n^2)

Step 2: sort both max array and min array, in O(n*lgn) time

Step 3: start from the biggest value in max array. subtract each one from min array from it until that c > a and d > b holds. then move down the max array by one, and repeat the same thing. would take O(n^2)

Step 4: step 3 would give a collection of n elements, find the biggest one in O(n).

I know it's complicated but does work in O(n^2) time.

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

1. create two dimensional array arrMax(x,y) and var res to store the result
2. for( x=n-1;x>0;x--) for (y=n-1;y>0;y--)
2.1 var maximumForY=if (y==n-1) then A(x,y) else max(arrMax(x,y+1),A(x,y))
2.2 arrMax(x,y)=max(maximumForY, (if(x==n-1) then A(x,y) else max(arrMax(x+1,y),A(x,y))))
2.3 if(x!=n-1 and y!=n-1) then (if((x==n-2 and y=n-2) or A(x,y)-arrMax(x+1,y+1)>res) then res=A(x,y)-arrMax(x+1,y+1)
3. return res
this solution? I haven't tried to code clearly, but the overall idea is somehow like this

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

Sorry that just read Yang's reply. Mine is basically same as Yang's but use the same loop to calculate the value of maximum value A(c,d) - A(a,b) only.

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

and sorry to Yang that I haven't gone through the replies before post

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

it is not n^2

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

Sort the matrix elements. store these with the indexes(linear or 2D). complexity - nlogn. search the elements for max diff starting with max - min from the sorted array. solution is the for which indexes c,d > a,b. worst case complexity n^2. for most cases the overall complexity would be better than n^2

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

It seems to me that it's more or less like: for a one dimensional array A[n], find maximum value A[a] - A[b], where a < b in O(n) time.

I think the array version can be solved by DP through distinguishing the ascension and descension of the values of elements in one-traversing, so does the matrix.

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

What I understood from this question is as follows:
For a given nxn matrix(array), the value A[i][j] represents value in ith row and jth column. Now, c and d (from A(c,d)) are to considered in such a way that their values should be greater than a and b (from A(a,b)) respectively. So, we can conclude that values of a and b cannot be equal to n( n-1 since arrays are zero indexed). Also, the values of c and d should be at least greater than a and b respectively by 1. So, considering these facts, I created following logic:

``````public static void max(int [][]arr)
{
int max = Integer.MIN_VALUE;
int n = arr.length;
int temp=0;
for(int a=0; a<(n-1); a++)
{
for(int b=0; b<(n-1); b++)
{
for(int c=a+1; c<n;c++)
{
for(int d=b+1; d<n;d++)
{
//System.out.println(a+" "+b+" "+c+" "+d+": value:"+(arr[c][d]-arr[a][b]));
if(max<(arr[c][d]-arr[a][b]))
max = arr[c][d]-arr[a][b];
}
}
}
}
System.out.println("Max:"+max);
}``````

``````Matrix input:
14	17	65
79	27	22
71	62	16
0 0 1 1: value:13
0 0 1 2: value:8
0 0 2 1: value:48
0 0 2 2: value:2
0 1 1 2: value:5
0 1 2 2: value:-1
1 0 2 1: value:-17
1 0 2 2: value:-63
1 1 2 2: value:-11
Max:48``````

Please suggest me if this code can be improvised further. Though it may seem that the complexity is worse than O(n^2), these iterations would only pic valid combinations only.

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

How about fixing the loop to traverse the matrix diagonally? One diagonal at a time.

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

In the above since u already have a comparision between 0011 and 1122, I think you can skip the 0022 comparision. If 1122 is negative then its not the max if positive then add the difference to 0011.
Similarly you can skip many comparisions.

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

@Aravind..
Could you explain your logic based on sample output provided. Please edit the code that suits your logic and comment here.

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

<?php
//\$num = array(3,8,5,9,7,1,2,4,6);
\$num = array (
array (8,5,2),
array (1,4,7),
array (3,9,6)
);
\$n = count(\$num);

\$result = \$num - \$num;
\$min_value = \$num;

//Complexity O(n^2)
for(\$i = 0; \$i < \$n-1; \$i++) {
for(\$j = 0; \$j < \$n-1; \$j++) {
\$min_value = min(\$min_value, \$num[\$i][\$j]);
\$result = max(\$result, \$num[\$i+1][\$j+1] - \$min_value);
printf("i:\$i j:\$j min_value: \$min_value result:\$result");
}
}
var_dump(\$result);
?>

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{<?php \$m = array ( array(9,8,1,6), array(5,2,2,3), array(7,4,16,11), array(6,1,8,15) ); \$n = count(\$m); \$max_diff = \$m - \$m; for(\$i = 0; \$i < \$n-1; \$i ++) { for(\$j = 0; \$j < \$n-1; \$j ++) { if (\$i == 0 && \$j == 0) { \$min_value = \$m  ; } elseif (\$i == 0 && \$j > 0) { \$min_value = min (\$min_value, \$m[\$j]); } elseif (\$j == 0 && \$i > 0) { \$min_value = min (\$min_value, \$m[\$j]); } else { \$min_value = min ( \$m[\$i][\$j], \$m [\$i-1][\$j], \$m[\$i][\$j - 1] ); } \$max_diff = max (\$max_diff, \$m[\$i+1][\$j+1] - \$min_value ); echo "i:\$i j:\$j min_value:\$min_value max_diff:\$max_diff" . "<br>"; } }
Comment hidden because of low score. Click to expand.
0

<?php
\$m = array
(
array(9,8,1,6),
array(5,2,2,3),
array(7,4,16,11),
array(6,1,8,15)
);
\$n = count(\$m);
\$max_diff = \$m - \$m;

for(\$i = 0; \$i < \$n-1; \$i ++) {
for(\$j = 0; \$j < \$n-1; \$j ++) {
if (\$i == 0 && \$j == 0) {
\$min_value = \$m  ;
}
elseif (\$i == 0 && \$j > 0) {
\$min_value = min (\$min_value, \$m[\$j]);
}
elseif (\$j == 0 && \$i > 0) {
\$min_value = min (\$min_value, \$m[\$j]);
} else {
\$min_value = min ( \$m[\$i][\$j], \$m [\$i-1][\$j], \$m[\$i][\$j - 1] );
}
\$max_diff = max (\$max_diff, \$m[\$i+1][\$j+1] - \$min_value );

echo "i:\$i j:\$j min_value:\$min_value max_diff:\$max_diff" . "<br>";
}
}

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

``````int findMaxDiff(vector<vector<int>> M)
{
int row = M.size();
if(row == 0)
return INT_MIN;
int col = M.size();
if(row == 1 || col == 1)
return INT_MIN;
int A[row][col];
int retV = INT_MIN;
for(int i=0; i<row; i++)
for(int j=0; j<col; j++)
{
A[i][j] = M[i][j];
if(i>0)
A[i][j] = min(A[i][j], A[i-1][j]);
if(j>0)
A[i][j] = min(A[i][j], A[i][j-1]);
if(i>0 && j>0)
retV = max(retV, M[i][j] - A[i-1][j-1]);
}
return retV;
}``````

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

If we convert the matrix into a vector then the maximum can be found the value in O(n^2). Here is the code

``````double MaxElement(std::vector<std::vector<double>> M)
{
int n1=M.size();
int n2=M.at(0).size();
std::vector<double> vec;
for (int i=0; i<n1 ;i++)
{
for(int j=0; j<n2; j++)
{
vec.push_back(M[i][j]);
}
}
int vecSize=vec.size();
double max=vec[n2+1]-vec;
int j=0;
for (int i=0; i<vecSize ; i++)
{
j=i+n2+1;
while(j<vecSize)
{
if (vec[j]-vec[i]>max)
{
max=vec[j]-vec[i];
}
if ((j+1)%n2>0)
{
j++;
}
else
{
j+=n2+1;
}
}

}
return max;
}``````

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

The following is in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MatrixMaxElement
{
class Program
{
static void Main(string[] args)
{
int[,] matrix = new int[3, 3];

FillArray(matrix);
Display(matrix);

Console.WriteLine(string.Format("\n\nMax Value is {0}",FindMax(matrix)));

}

private static void FillArray(int[,] matrix)
{
for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
matrix[i,j] = i + j;
}
}
}

private static void Display(int[,] matrix)
{
for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
Console.WriteLine("\n");
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
Console.Write(matrix[i, j]);
Console.Write("\t");
}
}
}

private static int FindMax(int[,] matrix)
{
int max = 0;

for (int i = 0; i <= matrix.GetUpperBound(0); i++)
{
for (int j = 0; j <= matrix.GetUpperBound(1); j++)
{
if (i == 2 || j == 2) continue;
int a = i;
int b = j;
int c = a + 1;
int d = b + 1;

var difference = matrix[c,d] - matrix[a,b];
if (difference > max)
max = difference;
}

}

return max;
}
}
}

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

int findmax(int a,int b,int R,int C){

int max=INT_MIN,j;

for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}

for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}

return mat[R-1][C-1];
}

use DP no need to even allocate extra space manipulate that matrix

ans =max-mat[a][b];

// if any prolem with this code plz let me know

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

``````int findmax(int a,int b,int R,int C){

int max=INT_MIN,j;

for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}

for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}

return mat[R-1][C-1];``````

}

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

``````a=a+1;
b=b+1;// as mentioned no extra space manipulate that matrix
int findmax(int a,int b,int R,int C){

int max=INT_MIN,j;

for(int i=a;i<R;i++){
max=maxm(max,mat[i][b]);
mat[i][b]=max;
}
max=INT_MIN;
for(int i=b;i<C;i++){
max=maxm(max,mat[a][i]);
mat[a][i]=max;
}

for(int i=a+1;i<R;i++)
for(int j=b+1;j<C;j++){
mat[i][j]=maxm(maxm(mat[i-1][j],mat[i][j-1]),mat[i][j]);
}

return mat[R-1][C-1];
}``````

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

``````//Considering 'n' a global variable representing size of matrix

//Considering matrix to be in the form of double dimension array of size (nXn )

public int maxDiffInMatrix(int arr[][]){
int max=arr;
int min=arr;
int a=0,b=0,c=1,d=1;

//Finding maximum arr[c][d].....complexity n^2
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(arr[i][j]>max){
max=arr[i][j];
c=i;
d=j;
}
}
}

//Finding minimum arr[a][b]........complexity n^2
for(int m=0;m<c;m++){
for(int n=0;n<d;n++){
if(arr[m][n]<min){
min=arr[m][n];
a=m;
b=n;
}
}
}
//Returning desired value.....final complexity: (n^2)+(n^2)= O(n^2)
return (arr[c][d]-arr[a][b]);
}``````

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

why this has got -1 vote?

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

``````public class MaxMinArray {

public static void calc(int[][] arr, int n, int c, int d) {
if(n<2 || c<1 || d<1)
return;

int[][] maxjperi = new int[n][n];
int[][] minjperi = new int[n][n];

for(int i = 0; i<n; i++) {
maxjperi[i] = 0;
for(int j=1; j<n; j++) {
maxjperi[i][j] = arr[i][j] >= arr[i][maxjperi[i][j-1]] ? j : maxjperi[i][j-1];

minjperi[i][j] = arr[i][j] <= arr[i][minjperi[i][j-1]] ? j : minjperi[i][j-1];

}
}

int iwithmax = 0;
int iwithmin = 0;

for(int i = 1; i < c; i++) {
iwithmax = arr[i][maxjperi[i][d-1]] >= arr[iwithmax][maxjperi[iwithmax][d-1]] ? i : iwithmax;
iwithmin = arr[i][minjperi[i][d-1]] <= arr[iwithmin][minjperi[iwithmin][d-1]] ? i : iwithmin;

}

if(arr[c][d] - arr[iwithmax][maxjperi[iwithmax][d-1]] > arr[c][d] - +arr[iwithmin][minjperi[iwithmin][d-1]]) {
System.out.println("index are "+iwithmax+" and "+maxjperi[iwithmax][d-1]);
} else {
System.out.println("index are "+iwithmin+" and "+minjperi[iwithmin][d-1]);
}
}

}``````

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

#!/usr/bin/python

def matrix_min(mat):
a = len(mat)
max_m = [[0 for i in range(0,a)]for j in range(0,a)]
# construct a matrix which save the maximum value of the
# submatrix mat[i][j] to mat[a-1][a-1]
for i in reversed(range(0,a)):
for j in reversed(range(0,a)):
if i == a-1 and j == a-1:
max_m[i][j] = mat[i][j]
elif i == a-1 and j < a-1:
max_m[i][j] = max(mat[i][j], max_m[i][j+1])
elif j == a-1 and i < a-1:
max_m[i][j] = max(mat[i][j],max_m[i+1][j])
else:
max_m[i][j] = max(mat[i][j],max_m[i][j+1],max_m[i+1][j])

max_value = 0
for i in range(0,a-1):
for j in range(0,a-1):
# compare the current value in mat with the maximum
# value in the summatrix max_x[i+1][j+1] to max_x[a-1][a-1]
max_value = max(max_value, max_m[i+1][j+1]-mat[i][j])

print max_value

mat = [[3,7,9,2],[6,11,5,8],[1,20,4,7],[3,21,5,18]]
matrix_min(mat)

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

``````#!/usr/bin/python

def matrix_min(mat):
a = len(mat)
max_m = [[0 for i in range(0,a)]for j in range(0,a)]
# construct a matrix which save the maximum value of the
# submatrix  mat[i][j] to mat[a-1][a-1]
for i in reversed(range(0,a)):
for j in reversed(range(0,a)):
if i == a-1 and j == a-1:
max_m[i][j] = mat[i][j]
elif i == a-1 and j < a-1:
max_m[i][j] = max(mat[i][j], max_m[i][j+1])
elif j == a-1 and i < a-1:
max_m[i][j] = max(mat[i][j],max_m[i+1][j])
else:
max_m[i][j] = max(mat[i][j],max_m[i][j+1],max_m[i+1][j])

max_value = 0
for i in range(0,a-1):
for j in range(0,a-1):
# compare the current value in mat with the maximum
# value in the summatrix max_x[i+1][j+1] to max_x[a-1][a-1]
max_value = max(max_value, max_m[i+1][j+1]-mat[i][j])

print max_value

mat = [[3,7,9,2],[6,11,5,8],[1,20,4,7],[3,21,5,18]]
matrix_min(mat)``````

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.