Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
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;
}
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;
}
Why recursion when the following code can do the same.
K=A;
for ( i=1;i<n;i++)
{
k= K*A;
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
int **fun_matrix(int **a,int **b)
{
int **c,i,j,k;
c=malloc(sizeof(*c)*3);
for(i=0;i<3;i++)
{
c[i]=malloc(sizeof(int)*3);
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
c[i][j]=0;
for(k=0;k<3;k++)
{
c[i][j]=c[i][j]+(a[i][k]*b[k][j]);
}
}
}
return c;
}
void main()
{
int **a,**c;
int i,j,time,k;
int index;
int **result;
printf("enter the index of square matrix\n");
scanf("%d",&index);
a=malloc(sizeof(*a)*index);
for(i=0;i<index;i++)
{
a[i]=malloc(sizeof(int)*index);
}
for(i=0;i<index;i++)
{
for(j=0;j<index;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<index;i++)
{
for(j=0;j<index;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
printf("How many time to multiply this matrix\n");
scanf("%d",&time);
result=a;
for(k=0;k<time;k++)
{
printf("this multiplication time=%d\n",k+1);
result=fun_matrix(result,a);
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
printf("%d\t",result[i][j]);
}
printf("\n");
}
}
}
How does this involve dynamic programming? It's a simple repeated-squares method, analogous to the problem of taking a power in log time.
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
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
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.
Simple!!
try
- Aakash01 July 27, 2012Mat 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; }