Quiz questions
0. Title: DP1
Description: predict the complexity of the code:
vector<vector<int > > v(100,vector <int> (100,-1) );
int func(int n,int m)
{
if((n==0)||(m==0))
{
return 0;
}
else
{
if(dp[m][n]!=-1)
{
return dp[m][n];
}
else
{
return func(n-1,m-2)+func(n-2,m-1);
}
0.O(n^2)
1.O(n logn)
2.O(2^n)
3.O(n^3)
1. Title: DP2
Description: predict the complexity of the code:
vector<vector<int > > v(100,vector <int> (100,-1) );
int func(int n,int m)
{
if((n==0)||(m==0))
{
return 0;
}
else
{
if(dp[m][n]!=-1)
{
return dp[m][n];
}
else
{ lli x;
int i;
for(i1;i<n;i++)
{
for(j=1;j<m;j++)
{
x=x+ func(n-i,m-j);
}
}
dp[m][n]=x;
return x;
}
0.O(n^3)
1.O(n^4)
2.O(2^n)
3.O(n^2)
2. Title: DP3
Description: Predict output of the following code: Input(7)
vector<int> dp(11,-1);
int func(int x)
{
if((x==0)||(x==1))
return 2;
else
{
if(dp[x]!=-1)
return dp[x];
else
{
dp[x]=func(x-1)+func(x-2);
return dp[x];
}
}
}
int main()
{
for(i=0;i<5;i++)
{
cout<<func(i)<<" ";
}
}
0.2 2 4 8 12
1.2 2 4 6 10
2.2 4 6 10 16
3. Title: DP4
Description: predict the complexity of the code:
vector<vector<int > > dp(100,vector <int> (100,-1) );
int func(int n,int m)
{ lli x;
if((n==0)||(m==0))
{
return 0;
}
else
{
if(dp[m][n]!=-1)
{
return dp[m][n];
}
else
{
dp[n][m]= func(n-1,m-2)+func(n-2,m-1);
return dp[n][m];
0.O(n^2)
1.O(n logn)
2.O(2^n)
3.O(n^3)
4. Title: DP5
Description: Complexity of matrix chain multiplication using Dynmaic Programming:
0.O(n^2)
1.O(n^3)
2.O(n^2 logn)
3.O(n^4)
5. Title: DP6
Description: Efficient (Memory) Table size of Matrix Chain Multipilcation of Matrix
A1 to AN:
0.O(n^2)
1.B. O(n^2/2)
2.C. O(n)
3.None of these
6. Title: DP7
Description: Predict True and False:
every Greedy Solution Can Be solved using dynamic Programming
0.True
1.False
7. Title: DP8
Description: Given two sequences A and B, what will be the length of the longest
subsequence
present in both of them if we define L[m][n] , LCS of strings A[1….m]
and B [1…..n] ?
0.L[i][j]=L[i-1][j-1]+1 , when A[i]==B[j]
1.L[i][j]=(abs(L[i-1][j]-L[i][j-1])+L[i][j-1]+L[i-1][j]) /2 , when A[i]!=B[j]
2.L[i][j]=max(L[i-1][j],L[i]][j-1]) , when A[i]!=B[j]
3.All of these
8. Title: DP9
Description: Given an array A consisting of n integers , we define beauty of the
array as maximum sum of some contiguous elements with performing atmost one
operation which is , you can multiply any subarray with ‘x’ but only once.
What will be the maximum subarray sum for this input
N=5,x=-2
A=[-3,8,-2,1,-6]
(Bonus :: Can you write the effiicient code for it ?)
0.0
1.22
2.24
3.12
9. Title: DP10
Description: Given two strings , what could be the best complexity that you can
solve in , the K-ordered LCS of the given strings ?
A k-ordered LCS is defined to be the LCS of two sequences if you are allowed to
change at most k elements in the first sequence to any value you wish to.
Defining N and M as the length of the given strings respectively.
0.O(N*M*logk)
1.O(N*M*k)
2.O(N*M)
3.O(N*k*logM)
