## 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));
Console.ReadLine();

}

//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
of 0 votes

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

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