## Amazon Interview Question for Software Engineer / Developers

• -1
of 1 vote

Country: United States
Interview Type: In-Person

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

This question relates to dynamic programming where in we reduce the number of multiplications by constructing a table(remember lowest common subsequence)
if matrices are of sizes compatible for multiplication
m(i,j)=0 if i==k(diagnol elements)
(Not sure butcheck dynamic programming)
m(i,j)=min(summation(i<=k<j)m(i,k)+m(k+1,j)+pi-1pkpj-1)

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

i don't quite get you...for product of n matrices you got to have n-1 multiplications, no matter how you group the matrices (is there a shortcut formula to multiply three or more matrices simultaneously?).

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

Every two matrix A(mxn size) and B(nxo size) will require mxnxo multiplication operations and result in a new matrix C(mxo size) . If we have A1A2........An matrices then what are the minimum multiplication we require to create a new single matrix Az the problem is discussed in Coremon book in full detail underthechapter related to dynamic programming. Also for online solution plz search chain matrix multiplication problem

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

but what if all the matrices are nxn matrix

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

It's the dynamic programming problem discussed in Cormen.

"The Artist" if all are n*n, then you are do iin any order. But for this problem, they are of different sizes, but can be multiplied.

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

Wikipedia article:
en.wikipedia.org/wiki/Matrix_chain_multiplication

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

yeah, i read that...good learning :)

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

It's about dynamic programming.
My idea is to split the Matrices into two sub Matrix[]. Then recursively calculating the result for each sub-Matrix, since there may be more than one way to split, we need to compare each kind of split and update the result that was supposed to be handed in to the upper level.
Here is my intact code, I tested with ABCD: A[10X30] B[30X5] C[5X60] D[60X4]

``````public class exercise {
static Matrix[] m = new Matrix;
public static void main( String[] args ){
m = new Matrix( 10, 30 );
m = new Matrix( 30, 5 );
m = new Matrix( 5, 60 );
m = new Matrix( 60, 4 );
exercise e = new exercise();
Result r = e.findMin(m);
System.out.println(r.s + " " + r.ct);
}

public Result findMin( Matrix[] m ) {
Result result = new Result();
int len = m.length;
int count = Integer.MAX_VALUE;
if( len == 1 ) {
String s = "("+m+")";
result = new Result( s, 0, m.r, m.c );
return result;
}
if( len == 2 ) {
String s = "(" + m+m+")";
result = new Result( s, m.r * m.c * m.c, m.r, m.c );
return result;
}
//split the m[]
for( int i = 0; i < len - 1; i++ ) {
ArrayList<Matrix> sub1 = new ArrayList<Matrix>();
ArrayList<Matrix> sub2 = new ArrayList<Matrix>();
for( int j = 0; j <= i; j++ ) {
sub1.add(m[j]);
}
for( int j = i + 1; j < len; j++ ) {
sub2.add(m[j]);
}
Result s1 = findMin( sub1.toArray( new Matrix[sub1.size()]) );
Result s2 = findMin( sub2.toArray( new Matrix[sub2.size()]) );
int newCount = s1.ct + s2.ct + s1.start * s2.start * s2.end;

String newStr = "(" + s1.s + ")(" +s2.s + ")";
//result = new Result( newStr, newCount, s1.start, s2.end );

if ( newCount < count ) {
count = newCount;
result = new Result( newStr, newCount, s1.start, s2.end );
}

//int[] sMerge = { newCount, s1, s2 };

//System.out.println(sub1.toString());
//System.out.println(sub2.toString());

}
return result;
}

class Result {
int ct;
String s;
int start;
int end;
public Result() {}
public Result( String str, int i, int st, int e ) {
ct = i;
s = str;
start = st;
end = e;
}
}
}
class Matrix {
int r;
int c;
public Matrix( int Row, int Col ) {
r = Row;
c = Col;

}
public String toString() {
return "[ " + r + " * " + c + " ] ";
}
}``````

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