## Amazon Interview Question

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

Could you please explain the question? Do you mean 'find sub matrix with maximum sum of its elements' of all the possible sub-matrices of the given matrix?

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

//Problem:
//================
//find maximum sum of matrix.

//Example:
//================
//a[i][j]

//i=0-SIZE
//j=0-SIZE

//1-23
//45-6
//789

//Result=1+3+4+5+7+8+9

//ALGO:
//================

//Keep on adding in the sum if( Negative Numbers ) then dont add else add.

//TEST CASES:
//================
//FUNCTIONAL

//1. All negative numbers
//3. all positive numbers
//4. all 32767 int value integers
//5. Characters

//N.FUNCTIONAL
//Perf
//1. Keep on passing the same Data[Time to execute should be same]
//Stress
//2. Test with large N*n matrix and see if there is no failure or degradation
//Security:
//3. Test with non valid integers \1 \2
//Globalisation
//4. Test with Kanji characjters[japanese] and unicode
//5. Test with a mix of integers and characters
//6. Test With Mix of Unicode and Special characters

//TEST HARNESS:
//================

using System;

namespace Problem
{
public class Solution
{
static void Main()
{
int X = Convert.ToInt16(Console.ReadLine());
int Y = Convert.ToInt16(Console.ReadLine());
int[][] Array = new int[X][]; //Declaring an 2D array X element

for (int i = 0; i < X; i++)
{
Array[i] = new int[Y]; //Declaring an 2D array Y element
for (int j = 0; j < Y; j++)
{
Random R = new Random(4);
int Random = R.Next(0, 9);
Array[i][j] = Random;
}
}

Console.WriteLine(MaxArraySum(Array));

}

//CODE:
//================

public static int MaxArraySum(int[][] A)
{
int Sum = 0;
int RowLen = A[0].Length;
int ColumnLen = A.Length;

for (int i = 0; i < RowLen; i++)
{
for (int j = 0; j < ColumnLen; j++)
{

if (A[i][j] > 0)
Sum += A[i][j];
}
}
return Sum;
}
}
}

//ORDER:
//================
//O(N^2)

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

Actually there is an O^3 algo to find max sum matrix...the idea should be finding an subarray having maimum sum...

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

Yes, indeed, the most practical is O(n^3) solution which is explained well here artofproblemsolving.com/Forum/viewtopic.php?t=39544

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.