Data Structure II Mock Test 8

1. For every rod cutting problem there will be a unique set of pieces that give the maximum price.

2. Which of the following errors will occur when the below code is executed?

#include<stdio.h>
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 100;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

3. What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?

 
#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[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%d\n",ans);
      return 0;
}

4. 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?

5. What is the output of the following program?

#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[] = {-20, 23, 10, 3, -10, 11, -5},len = 7;
     int ans = maximum_subarray_sum(arr, len);
     printf("%d",ans);
     return 0;
}

6. Which of the following is the longest common subsequence between the strings "hbcfgmnapq" and "cbhgrsfnmq" ?

7. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

8. Consider the following recursive implementation of the rod cutting problem:

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
      if(a > b)
            return a;
      return b;
}
int rod_cut(int *prices, int len)
{
      int max_price = INT_MIN; // INT_MIN is the min value an integer can take
      int i;
      if(len <= 0 )
	return 0;
      for(i = 0; i < len; i++)
	 max_price = max_of_two(_____________); // subtract 1 because index starts from 0
      return max_price;
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
      int ans = rod_cut(prices, len_of_rod);
      printf("%d",ans);
      return 0;
}

Complete the above code.

9. What is the output of the following code?

#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;
}

10. What is the output of the following code?

#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      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(s[i - 1] == rev[j - 1])
                arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "efgfe";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}