Data Structure · all questions

Dynamic Programming in Data Structures
practice.

Practice every MCQ with options. Use Show answers when you want the correct option and solution.

301

Questions

11/16

Page

Pick an option on a question to see the right answer and solution.

Q201

Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?

Select an option to see the answer and solution.

Q202

You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?

Select an option to see the answer and solution.

Q203

What is the output of the following program?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	    tmp_max = 0;
	    for(j = 0; j < i; j++)
	    {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		       tmp_max = LIS[j];
	        }
            }
	    LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	  if(LIS[i] > max)
	      max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

Select an option to see the answer and solution.

Q204

What is the value stored in sum[4] after the following program is executed?

#include<stdio.h>
int max_num(int a,int b)
{
      if(a> b)
	  return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	   sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	  if(sum[idx] > mx)
	      mx =sum[idx];
      return mx;
}
int main()
{
      int arr[] = {-2, 14, 11, -13, 10, -5, 11, -6, 3, -5},len = 10;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

Select an option to see the answer and solution.

Q205

What is the value stored in arr[3][3] when the following code is executed?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      for(i = 0; i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
                if(str1[i-1] == str2[j - 1])
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                    arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len][len];
}
int main()
{
      char str1[] = "ababcdabba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

Select an option to see the answer and solution.

Q206

What is the time complexity of the following dynamic programming implementation of the balanced partition problem where "n" is the number of elements and "sum" is their sum?

#include<stdio.h>
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

Select an option to see the answer and solution.

Q207

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

Select an option to see the answer and solution.

Q208

Consider the strings "PQRSTPQRS" and "PRATPBRQRPS". What is the length of the longest common subsequence?

Select an option to see the answer and solution.

Q209

Consider the following code snippet:

int max_sum_rectangle(int arr[][3],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
                  ______;
           }
      }
      return mx_sm;
}

Which of the following lines should be inserted to complete the above code?

Select an option to see the answer and solution.

Q210

What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      for(i = 0; i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
               if(str1[i-1] == str2[j - 1])
                   arr[i][j] = 1 + arr[i - 1][j - 1];
               else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len][len];
}
int main()
{
     char str1[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

Select an option to see the answer and solution.

Q211

Which of the following methods can be used to solve the edit distance problem?

Select an option to see the answer and solution.

Q212

What is the time complexity of the following dynamic programming implementation of the edit distance problem where "m" and "n" are the lengths of two strings?

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

Select an option to see the answer and solution.

Q213

What is the output of the following program?

#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
      int j, idx, jumps[len];
      jumps[len - 1] = 0;
      for(idx = len - 2; idx >= 0; idx--)
      {	
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
	        if(jumps[idx + j] + 1 < tmp_min)
		  tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
      }
      return jumps[0];
}
int main()
{
      int arr[] ={9, 9, 9, 9, 9, 9, 9, 9, 9},len = 9;
      int ans = min_jump(arr,len);
      printf("%d\n",ans);
      return 0;
}

Select an option to see the answer and solution.

Q214

What is the time complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

Select an option to see the answer and solution.

Q215

For which of the following inputs would Kadane's algorithm produce a WRONG output?

Select an option to see the answer and solution.

Q216

Which of the following methods can be used to find the nth Catalan number?

Select an option to see the answer and solution.

Q217

What is the space complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

Select an option to see the answer and solution.

Q218

Which of the following problems should be solved using dynamic programming?

Select an option to see the answer and solution.

Q219

Consider the following recursive implementation:

#include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
     int idx;
     if(strt == end)
	return 0;
     if(arr[strt] == 0) // jump cannot be made
	return INT_MAX;
     int min = INT_MAX;
     for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
     {
	  int jumps = min_jumps(____,____,____) + 1;
	  if(jumps < min)
	      min  = jumps;
     }
     return min;
}
int main()
{
     int arr[] ={1, 3, 5, 8, 9, 2, 6, 7, 6},len = 9;
     int ans = min_jumps(arr, 0, len-1);
     printf("%d\n",ans);
     return 0;
}

Which of these arguments should be passed by the min_jumps function represented by the blanks?

Select an option to see the answer and solution.

Q220

What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
          for(j = 1; j <= len2; j++)
          {
              if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
              else
                  arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

Select an option to see the answer and solution.

Prev 9 10 11 12 13 Next