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[0][0],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;}
}
}

- kg October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

had a naive solution...

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.

- jason October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

how about:
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

- William October 08, 2013 | Flag Reply
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.

- William October 08, 2013 | Flag
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

- William October 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is not n^2

- kumar October 21, 2013 | Flag
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

- sjs November 25, 2013 | Flag Reply
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.

- Chen October 07, 2013 | Flag Reply
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);
    }

Sample output for your reference:

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.

- Amit Petkar October 07, 2013 | Flag Reply
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.

- Anonymous October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Aravind October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amit Petkar October 07, 2013 | Flag
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[1][1] - $num[0][0];
$min_value = $num[0][0];

//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);
?>

- wusuopubupt October 09, 2013 | Flag Reply
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[1][1] - $m[0][0]; for($i = 0; $i < $n-1; $i ++) { for($j = 0; $j < $n-1; $j ++) { if ($i == 0 && $j == 0) { $min_value = $m [0] [0]; } elseif ($i == 0 && $j > 0) { $min_value = min ($min_value, $m[0][$j]); } elseif ($j == 0 && $i > 0) { $min_value = min ($min_value, $m[$j][0]); } 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>"; } } - wusuopubupt October 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

<?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[1][1] - $m[0][0];

for($i = 0; $i < $n-1; $i ++) {
for($j = 0; $j < $n-1; $j ++) {
if ($i == 0 && $j == 0) {
$min_value = $m [0] [0];
}
elseif ($i == 0 && $j > 0) {
$min_value = min ($min_value, $m[0][$j]);
}
elseif ($j == 0 && $i > 0) {
$min_value = min ($min_value, $m[$j][0]);
} 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>";
}
}

- wusuopubupt October 10, 2013 | Flag
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[0].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;
 }

- Jason October 15, 2013 | Flag Reply
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[0];
	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;
}

- Sadaf November 16, 2013 | Flag Reply
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;
using System.Threading.Tasks;

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

Console.Read();

}

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

- Bharry December 07, 2013 | Flag Reply
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

- Anonymous December 20, 2013 | Flag Reply
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];

}

- Anonymous December 20, 2013 | Flag Reply
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];
}

- Anonymous December 20, 2013 | Flag Reply
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[1][1];
		int min=arr[0][0];
		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]);
	}

- ankit.hbtik October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why this has got -1 vote?

- jyothi ganesh December 15, 2013 | Flag
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] = 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]);
		}
	}

}

- joyboyhardik October 08, 2013 | Flag Reply
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)

- Yang October 08, 2013 | Flag Reply
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)

- Yang October 08, 2013 | 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