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?

- sdm on March 12, 2010 | Flag Reply
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)

- Tarun Phaugat on March 12, 2010 | Flag Reply
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...

- Nop on March 12, 2010 | Flag
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

- suleimenov on March 13, 2010 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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