## Amazon Interview Question Software Engineer / Developers

• 0

You are given a matrix multiplication function which takes two matrix and returns resultant matrix. I have a square matrix A. Write code to find A^n.

Country: India
Interview Type: Phone Interview

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

Simple!!
try

``````Mat calc( Mat A , int n )
{
if( n == 1 )  return A;
Mat temp = calc ( A , n/2 );
temp = tempxtemp;  // matrix multiplication
if( n%2 == 1 ) temp = tempxA;  // matrix multiplication
return temp;
}``````

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

With slight modification.

Mat calc( Mat A , int n )
{if( n == 2 ) return calc(A,A);
Mat temp = calc ( A , n/2 );
temp = tempxtemp; // matrix multiplication
if( n%2 == 1 )
temp = tempxA; // matrix multiplication
return temp;
}

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

Mat calc( Mat A , int n )
{if( n == 2 ) return calc(A,A);--- shud be A*A
Mat temp = calc ( A , n/2 );
temp = tempxtemp; // matrix multiplication
if( n%2 == 1 )
temp = tempxA; // matrix multiplication
return temp;
}

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

Why recursion when the following code can do the same.

K=A;

for ( i=1;i<n;i++)
{
k= K*A;
}

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

We've to use the function they are providing us to do Matrix multiplication

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

Using n/2 is not necessary. It still takes k*T (T is the time cost to do a single matrix multiplication) on the kth recursion level. Thus the total running time is still O(T*n).

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

Seems to be lg(n) * [matrix multiplication time] algorithm.

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

Dynamic programming method can solve matrix chain multiplication of all sizes using minimum number of multiplication to watch and understand that you can see this wonderful video

youtu.be/OSkllTB2aW4

However for this special case of same square matrix divide and conquer is sufficient

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

``````Let the function to calculate multiplications is calc(Mat A1, Mat A2)
calculate(Mat A, int n) {
Mat temp = A
if( n == 1){
return A
}
for(int i = 1; i < n -1; i++){
temp = calc(temp, A)
}
return temp
}``````

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

matrix cal(matrix A,int n)
{
matrix result=matrix::indentity;
matrix tmp=A;
for(;n;n>>1)
{
if(n&1)
{
result=result*tmp;
}
tmp*=tmp;
}
return result;
}

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

you can do this in log(n) .jst multiply till a^(n/2)*a^(n%2).

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

This is dynamic programming where we need to find minimum steps to n.

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

How does this involve dynamic programming? It's a simple repeated-squares method, analogous to the problem of taking a power in log time.

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

Breaking in sub problems can give better run time. To decide how to break, we need DP

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

I think the whole purpose here is to minimize the calls to multiplication function... and to know that we need DP.
For e.g say we need to find A^11... you solution will call Multiplication 5 times whereas the optimized way to solve this would be to call mult 4 times

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

We do not need a dynamic programming here as the size of all the matrix are same for example if A is pXq and B is qXr then C=AB takes pqr multiplication (cost) Now lets say here all matrix are square matrix of size nXn and whatever way you multiply it will take the same cost so we can better use divide and conquer method which will take log(N) base 2 steps if number of square matrix to multiply is N
However the dynamic programming method can solve matrix chain of all sizes using minimum number of multiplication to watch and understand that you can see this wonderful video

youtu.be/OSkllTB2aW4

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

Agree with the above comment, This is a simple problem similar to that of finding pow(x,n) in min number of calculations. since the matrices here are square matrices so using DP would give the same answer(i.e.) number of calculations no matter what. +1 to the above comment by annonymous.

Name:

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

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.