-
predict the complexity of the code:
vector<vector > v(100,vector (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);
}}
}
I think that because they are not putting any element in dp so dp is not in use, which implies order should be 2^n??
2) Efficient (Memory) Table size of Matrix Chain Multipilcation of Matrix A1 to AN:
O(n^2)
B. O(n^2/2)
C. O(n)
None of these
- 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] ?
L[i][j]=L[i-1][j-1]+1 , when A[i]==B[j]
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]
L[i][j]=max(L[i-1][j],L[i]][j-1]) , when A[i]!=B[j]
All of these
I do not understand what is meant by 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] - 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
22
24
12
I am not able to understand the question. Please explain. - 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.
O(NMlogk)
O(NMk)
O(N*M)
O(NklogM)
