Q.1
Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
  • a) Greedy algorithm
  • b) Recursion
  • c) Dynamic programming
  • d) Both recursion and dynamic programming
Q.2
In which of the following cases the minimum no of insertions to form palindrome is maximum?
  • a) String of length one
  • b) String with all same characters
  • c) Palindromic string
  • d) Non palindromic string
Q.3
In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
  • a) True
  • b) False
Q.4
Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?
  • a) 0
  • b) 1
  • c) 2
  • d) 3
Q.5
Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
  • a) 0
  • b) 1
  • c) 2
  • d) 3
Q.6
Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
  • a) Minimum number of jumps problem
  • b) Longest common subsequence problem
  • c) Coin change problem
  • d) Knapsack problems
Q.7
Consider the following dynamic programming implementation: #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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]); } } return _____________; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return}
  • a) arr[len][len]
  • b) len + arr[len][len]
  • c) len
  • d) len – arr[len][len]
Q.8
What is the time complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem? #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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]); } } return len - arr[len][len]; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return}
  • a) O(1)
  • b) O(n)
  • c) O(n2)
  • d) O(mn)
Q.9
What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem? #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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]); } } return len - arr[len][len]; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return}
  • a) O(1)
  • b) O(n)
  • c) O(n2)
  • d) O(mn)
Q.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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]); } } return len - arr[len][len]; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return}
  • a) 1
  • b) 2
  • c) 3
  • d) 4
Q.11
What is the value stored in arr[2][when the following code is executed? #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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ else arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]); } } return len - arr[len][len]; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return}
  • a) 2
  • b) 3
  • c) 4
  • d) 5
Q.12
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][= for(i =i <= len; i++) arr[0][i] = for(i =i <= len; i++) { for(j =j <= len; j++) { if(s[i -== rev[j - 1]) arr[i][j] = arr[i - 1][j -+ 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}
  • a) 0
  • b) 2
  • c) 4
  • d) 6
0 h : 0 m : 1 s