Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

Multiple choice question for engineering

Set 1

1. Which of the following methods can be used to solve the longest palindromic subsequence problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) All of the mentioned

View Answer

Answer: d [Reason:] All of the mentioned methods can be used to solve the longest palindromic subsequence problem.

2. Which of the following strings is a palindromic subsequence of the string “ababcdabba”?
a) abcba
b) abba
c) abbbba
d) all of the mentioned

View Answer

Answer: d [Reason:] All of the mentioned strings are palindromic subsequences of the string “ababcdabba”.

3. For which of the following, the length of the string is equal to the length of the longest palindromic subsequence?
a) A string that is a palindrome
b) A string of length one
c) A string that has all the same letters(e.g. aaaaaa)
d) All of the mentioned

View Answer

Answer: d [Reason:] In all the above cases, the string itself is the longest palindromic subsequence and hence the length of the longest palindromic subsequence is equal to the length of the string.

4. What is the length of the longest palindromic subsequence for the string “ababcdabba”?
a) 6
b) 7
c) 8
d) 9

View Answer

Answer: b [Reason:] The longest palindromic subsequence is “abbabba” and its length is 7.

5. What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?
a) O(1)
b) O(2n)
c) O(n)
d) O(n2)

View Answer

Answer: b [Reason:] In the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. This takes exponential time.

6. For every non-empty string, the length of the longest palindromic subsequence is at least one.
a) True
b) False

View Answer

Answer: a [Reason:] A single character of any string can always be considered as a palindrome and its length is one.

7. Longest palindromic subsequence is an example of ______________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

View Answer

Answer: b [Reason:] Longest palindromic subsequence is an example of 2D dynamic programming.

8. Consider the following code:

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

Which of the following lines completes the above code?
a) strrev(str2)
b) str2 = str1
c) len2 = strlen(str2)
d) none of the mentioned

View Answer

Answer: a [Reason:] To find the longest palindromic subsequence, we need to reverse the copy of the string, which is done by strrev.

9. What is the time complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?
a) O(n)
b) O(1)
c) O(n2)
d) None of the mentioned

View Answer

Answer: c [Reason:] The time complexity of the above dynamic programming implementation to find the longest palindromic subsequence is O(n2).

10. What is the space complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?
a) O(n)
b) O(1)
c) O(n2)
d) None of the mentioned

View Answer

Answer: c [Reason:] The space complexity of the above dynamic programming implementation to find the longest palindromic subsequence is O(n2).

11. 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;
}

a) 2
b) 3
c) 4
d) 5

View Answer

Answer: a [Reason:] The value stored in arr[3][3] when the above code is executed is 2.

12. 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 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[] = "abcd";
int ans = lps(str1);
printf("%d",ans);
return 0;
}

a) 0
b) 1
c) 2
d) None of the mentioned

View Answer

Answer: b [Reason:] The program prints the length of the longest palindromic subsequence, which is 1.

13. 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 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[] = "abdgkagdjbccbba";
int ans = lps(str1);
printf("%d",ans);
return 0;
}

a) 5
b) 7
c) 9
d) 11

View Answer

Answer: c [Reason:] The program prints the length of the longest palindromic subsequence, which is 9.

Set 2

1. Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
a) Dynamic programming
b) Two for loops (naive method)
c) Divide and conquer
d) All of the mentioned

View Answer

Answer: d [Reason:] All of the methods mentioned can be used to solve the maximum sub-array sum problem.

2. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6

View Answer

Answer: b [Reason:] The maximum sub-array sum is 5.

3. Find the maximum sub-array sum for the given elements.
{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1

View Answer

Answer: d [Reason:] All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.

4. Consider the following naive method to find the maximum sub-array sum:

#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}

Which line should be inserted to complete the above code?
a) tmp_max = cur_max
b) break
c) continue
d) cur_max = tmp_max

View Answer

Answer: d [Reason:] If the tmp_max element is greater than the cur_max element, we make cur_max equal to tmp_max, i.e. cur_max = tmp_max.

5. What is the time complexity of the naive method used to find the maximum sub-array sum in an array containing n elements?
a) O(n2)
b) O(n)
c) O(n3)
d) O(1)

View Answer

Answer: a [Reason:] The naive method uses two for loops. The outer loop runs from 0 to n, i.e. i = 0 : n. The inner loop runs from i to n, i.e. j = i : n. Therefore, the inner loop runs: n times when the outer loop runs the first time. (n-1) times when the outer loop runs the second time. : : : 2 times when the outer loop runs (n-1)th time. 1 time when the outer loop runs nth time. Therefore, time complexity = n + (n-1) + (n-2) + …… + 2 + 1 = n * (n + 1) /2 = O(n2).

6. What is the space complexity of the naive method used to find the maximum sub-array sum in an array containing n elements?
a) O(n2)
b) O(1)
c) O(n3)
d) O(n)

View Answer

Answer: b [Reason:] The naive method uses only a constant space. So, the space complexity is O(1).

7. What is the output of the following naive method used to find the maximum sub-array sum?

#include<stdio.h>
int main()
{
int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max = 0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max += arr[sub_arr_idx];
if(tmp_max > cur_max)
cur_max = tmp_max;
}
}
printf("%d",cur_max);
return 0;
}

a) 6
b) 9
c) 7
d) None of the mentioned

View Answer

Answer: c [Reason:] The naive method prints the maximum sub-array sum, which is 7.

8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)

View Answer

Answer: c [Reason:] The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).

9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)

View Answer

Answer: b [Reason:] The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).

Set 3

1. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

#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] = _______________________;
int mx = sum[0];
for(idx = 0; idx < len; idx++)
if(sum[idx] > mx)
mx =sum[idx];
return mx;
}
int main()
{
int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
int ans = maximum_subarray_sum(arr, len);
printf("%d",ans);
return 0;
}

a) max_num(sum[idx – 1] + arr[idx], arr[idx])
b) sum[idx – 1] + arr[idx].
c) min_num(sum[idx – 1] + arr[idx], arr[idx])
d) arr[idx].

View Answer

Answer: a [Reason:] The array “sum” is used to store the maximum sub-array sum. The appropriate way to do this is by using: sum[idx] = max_num(sum[idx – 1] + arr[idx], arr[idx]).

2. What is the time complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)

View Answer

Answer: a [Reason:] The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).

3. What is the space complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)

View Answer

Answer: a [Reason:] The above dynamic programming algorithm uses space equal to the length of the array to store the sum values. So, the space complexity is O(n).

4. Consider the following code snippet:

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Which property is shown by line 4 of the above code snippet?
a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) None of the mentioned

View Answer

Answer: a [Reason:] The current sum (i.e. sum[idx]) uses the previous sum (i.e. sum[idx – 1]) to get an optimal value. So, line 4 shows the optimal substructure property.

5. Consider the following code snippet:

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Which method is used by line 4 of the above code snippet?
a) Divide and conquer
b) Recursion
c) Both memoization and divide and conquer
d) Memoization

View Answer

Answer: d [Reason:] The array “sum” is used to store the previously calculated values, so that they aren’t recalculated. So, line 4 uses the memoization technique.

6. Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}
a) 33
b) 36
c) 23
d) 26

View Answer

Answer: b [Reason:] All the elements of the array are positive. So, the maximum sub-array sum is equal to the sum of all the elements, which is 36.

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

a) 27
b) 37
c) 36
d) 26

View Answer

Answer: b [Reason:] The program prints the value of maximum sub-array sum, which is 37.

8. 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;
}

a) 28
b) 25
c) 22
d) 12

View Answer

Answer: c [Reason:] After the program is executed the value stored in sum[4] is 22. Note: You are asked to find the value stored in sum[4] and NOT the output of the program.

Set 4

1. QuickSort can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming

View Answer

Answer: b [Reason:] First you divide(partition) the array based on the pivot element and sort accordingly.

2. Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array,
partition returns the pivot element, we will see the code for partition very soon)
a)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}

b)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high<low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}

c)

public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot);
quickSort(arr, pivot, high);
}
}

d) None of the mentioned

View Answer

Answer: a [Reason:] Based on the pivot returned by the call to partition, recursive calls to quickSort sort the given array.

3. What is the worst case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

View Answer

Answer: d [Reason:] When the input array is already sorted.

4. What is a randomized QuickSort?
a) The leftmost element is chosen as the pivot
b) The rightmost element is chosen as the pivot
c) Any element in the array is chosen as the pivot
d) A random number is generated which is used as the pivot

View Answer

Answer: c [Reason:] QuickSort is randomized by placing the input data in the randomized fashion in the array or by choosing a random element in the array as a pivot.

5. Which of the following code performs the partition operation in QuickSort?
a)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left > right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}

b)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left <= right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}

c)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left <= right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}

d)

private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left > right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}

View Answer

Answer: b [Reason:] The array is partitioned such that the elements left to the pivot are lesser than the pivot while the elements right of the pivot are greater than the pivot.

6. What is the best case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

View Answer

Answer: a [Reason:] The array is partitioned into equal halves, using the Divide and Conquer master theorem, the complexity is found to be O(nlogn).

7. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 3
b) 3 and 1
c) 2 and 6
d) 6 and 2

View Answer

Answer: a [Reason:] The call to partition returns 1 and 3 as the pivot elements.

8. What is the average case complexity of QuickSort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

View Answer

Answer: a [Reason:] The position of partition(split) is unknown, hence all(n) possibilities are considered, the average is found by adding all and dividing by n.

9. The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 6
b) 6 and 1
c) 2 and 6
d) None of the mentioned

View Answer

Answer: d [Reason:] There is only one pivot with which the array will be sorted, the pivot is 1.

10. Which of the following is not true about QuickSort?
a) in-place algorithm
b) pivot position can be changed
c) adaptive sorting algorithm
d) can be implemented as a stable sort

View Answer

Answer: b [Reason:] Once a pivot is chosen, its position is finalized in the sorted array, it cannot be modified.

Set 5

1. You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?
a) Dynamic Programming
b) Greedy Algorithm
c) Recursion
d) All of the mentioned

View Answer

Answer: d [Reason:] Both recursion and dynamic programming can be used to solve minimum number of jumps problem.

2. Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a) 1
b) 2
c) 3
d) 4

View Answer

Answer: c [Reason:] The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.

3. 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("%dn",ans);
return 0;
}

Which of these arguments should be passed by the min_jumps function represented by the blanks?
a) arr, strt + idx, end
b) arr + idx, strt, end
c) arr, strt, end
d) arr, strt, end + idx

View Answer

Answer: a [Reason:] arr, strt + idx, end should be passed as arguments.

4. For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
a) True
b) False

View Answer

Answer: a [Reason:] Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}. In both the cases the number of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in multiple ways using minimum number of jumps.

5.What is the output of the following program?

#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(arr, strt + idx, end) + 1;
if(jumps < min)
min  = jumps;
}
return min;
}
int main()
{
int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9;
int ans = min_jumps(arr, 0, len-1);
printf("%dn",ans);
return 0;
}

a) 4
b) 5
c) 6
d) 7

View Answer

Answer: a [Reason:] The program prints the minimum number of jumps required to reach the end of the array. One way reach the end using minimum number of jumps is {1 -> 2 -> 4 -> 8 -> 9}. So, the number of jumps is 4.

6. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
a) True
b) False

View Answer

Answer: b [Reason:] Consider the array {1,0,2,3,4}. In this case, only one element is 0 but it is not possible to reach the end of the array.

7. Consider the following dynamic programming implementation of the minimum jumps problem:

#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("%dn",ans);
return 0;
}

Which of the following “for” loops can be used instead of the inner for loop so that the output doesn’t change?
a) for(j = 1; j < arr[idx] + len; j++)
b) for(j = 0; j < arr[idx] – len; j++)
c) for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)
d) None of the mentioned

View Answer

Answer: d [Reason:] None of the above mentioned “for” loops can be used instead of the inner for loop. Note, for(j = idx + 1; j < len && j <= arr[idx] + idx; j++) covers the same range as the inner for loop but it produces the wrong output because the indexing inside the loops changes as “j” takes different values in the two “for” loops.

8. What is the time complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

View Answer

Answer: c [Reason:] The time complexity of the above dynamic programming implementation is O(n2).

9. What is the space complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

View Answer

Answer: b [Reason:] The space complexity of the above dynamic programming implementation is O(n).

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

a) 7
b) 8
c) 9
d) 10

View Answer

Answer: b [Reason:] The program prints the minimum jumps required to reach the end of the array, which is 8 and so the output is 8.

11. 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("%dn",ans);
return 0;
}

a) 1
b) 6
c) 2
d) 7

View Answer

Answer: a [Reason:] The program prints the minimum jumps required to reach the end of the array, which is 1 and so the output is 1.