This set of Data Structure Assessment Questions and Answers focuses on “Minimum Insertions to form a Palindrome”.
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
View Answer
Explanation: Dynamic programming and recursion can be used to solve the problem.
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
View Answer
Explanation: In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.
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
View Answer
Explanation: In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string “abc”. The string can be converted to “abcba” by inserting “a” and “b”. The number of insertions is two, which is equal to length minus one.
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
View Answer
Explanation: The string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. Thus, only one insertion is required.
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
View Answer
Explanation: The given string is already a palindrome. So, no insertions are required.
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
View Answer
Explanation: A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.
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][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 _____________; } int main() { char s[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return 0; }
Which of the following lines should be added to complete the code?
a) arr[len][len]
b) len + arr[len][len]
c) len
d) len – arr[len][len]
View Answer
Explanation: arr[len][len] contains the length of the longest palindromic subsequence. So, len – arr[len][len] gives the minimum number of insertions required to form a palindrome.
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][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[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return 0; }
a) O(1)
b) O(n)
c) O(n2)
d) O(mn)
View Answer
Explanation: The time complexity of the above dynamic programming implementation is O(n2).
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][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[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return 0; }
a) O(1)
b) O(n)
c) O(n2)
d) O(mn)
View Answer
Explanation: The space complexity of the above dynamic programming implementation is O(n2).
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[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return 0; }
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The length of the longest palindromic subsequence is 3. So, the output will be 5 – 3 = 2.
11. What is the value stored in arr[2][4] 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][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[] = "abcda"; int ans = min_ins(s); printf("%d",ans); return 0; }
a) 2
b) 3
c) 4
d) 5
View Answer
Explanation: The value stored in arr[2][4] 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(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; }
a) 0
b) 2
c) 4
d) 6
View Answer
Explanation: Since the string “efgfe” is already a palindrome, the number of insertions required is 0.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Check Programming Books
- Practice Programming MCQs
- Practice Data Structure MCQ
- Check Computer Science Books