Q.1 What does LCS stand for in dynamic programming?
Longest Common Substring
Longest Common Subsequence
Largest Common Sequence
Longest Continuous Subsequence
Explanation - LCS stands for Longest Common Subsequence, a classic DP problem of finding the longest subsequence common to two sequences.
Correct answer is: Longest Common Subsequence
Q.2 Which approach is commonly used to solve LCS?
Greedy
Divide and Conquer
Dynamic Programming
Brute Force only
Explanation - Dynamic Programming is the efficient way to solve LCS in O(m*n) time compared to brute force exponential solutions.
Correct answer is: Dynamic Programming
Q.3 What is the time complexity of the standard DP solution for LCS with strings of length m and n?
O(m+n)
O(m*n)
O(2^(m+n))
O(log(m+n))
Explanation - The DP solution fills a matrix of size m*n, leading to O(m*n) complexity.
Correct answer is: O(m*n)
Q.4 If X = 'ABCBDAB' and Y = 'BDCABA', what is the length of their LCS?
3
4
5
6
Explanation - The LCS is 'BCBA' or 'BDAB', both of length 4.
Correct answer is: 4
Q.5 What is the space complexity of the naive DP LCS algorithm?
O(1)
O(m+n)
O(m*n)
O(2^(m+n))
Explanation - The DP matrix requires O(m*n) space to store intermediate results.
Correct answer is: O(m*n)
Q.6 Which technique reduces the space complexity of LCS DP?
Tabulation
Divide and Conquer
Space Optimization
Backtracking
Explanation - By storing only two rows at a time, space can be reduced from O(m*n) to O(min(m,n)).
Correct answer is: Space Optimization
Q.7 The LCS problem is an application of?
Greedy Algorithms
Graph Theory
Dynamic Programming
Number Theory
Explanation - LCS relies on overlapping subproblems and optimal substructure, both core DP concepts.
Correct answer is: Dynamic Programming
Q.8 In LCS, what is the recurrence relation when last characters match?
LCS[i][j] = 0
LCS[i][j] = LCS[i-1][j-1] + 1
LCS[i][j] = LCS[i-1][j]
LCS[i][j] = LCS[i][j-1]
Explanation - If characters match, we add 1 to the result of the remaining subsequences.
Correct answer is: LCS[i][j] = LCS[i-1][j-1] + 1
Q.9 In LCS, what is the recurrence relation when last characters don’t match?
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
LCS[i][j] = LCS[i-1][j-1]
LCS[i][j] = LCS[i][j]+1
LCS[i][j] = 0
Explanation - If characters don’t match, we consider skipping one character from either string.
Correct answer is: LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
Q.10 What is the LCS length of X='AXYT' and Y='AYZX'?
1
2
3
4
Explanation - The LCS is 'AY' of length 2.
Correct answer is: 2
Q.11 Which type of substructure does LCS exhibit?
Greedy-choice
Overlapping Subproblems
No substructure
Backtracking
Explanation - LCS reuses solutions to smaller subproblems repeatedly, a key DP feature.
Correct answer is: Overlapping Subproblems
Q.12 Which algorithm is faster for LCS: brute force or DP?
Brute Force
Dynamic Programming
Both same
Depends on input
Explanation - Brute force is exponential while DP reduces it to polynomial O(m*n).
Correct answer is: Dynamic Programming
Q.13 What will LCS('ABC', 'AC') return?
'A'
'C'
'AC'
'BC'
Explanation - The LCS is 'AC', length 2.
Correct answer is: 'AC'
Q.14 If one string is empty, what is the LCS length?
0
1
Length of other string
Undefined
Explanation - An empty string has no common subsequence with any other string.
Correct answer is: 0
Q.15 Which problem is LCS most similar to?
Matrix Chain Multiplication
Activity Selection
Edit Distance
Knapsack Problem
Explanation - Both LCS and Edit Distance use DP tables and character comparisons.
Correct answer is: Edit Distance
Q.16 What is the LCS of 'XMJYAUZ' and 'MZJAWXU'?
'MJAU'
'XJU'
'MZJU'
'MJAU'
Explanation - The LCS of the given strings is 'MJAU' of length 4.
Correct answer is: 'MJAU'
Q.17 Which method is used to reconstruct LCS after computing the table?
Greedy search
Backtracking
Divide and Conquer
Recursion
Explanation - The LCS is reconstructed by backtracking from the bottom-right of the DP table.
Correct answer is: Backtracking
Q.18 For X='AAAA' and Y='AA', what is the LCS length?
1
2
3
4
Explanation - The common subsequence 'AA' of length 2 exists.
Correct answer is: 2
Q.19 Does LCS problem have optimal substructure property?
Yes
No
Sometimes
Only for equal length strings
Explanation - LCS has optimal substructure as the solution builds from smaller subproblems.
Correct answer is: Yes
Q.20 What is the maximum length of LCS of two strings?
Length of shorter string
Length of longer string
Sum of lengths
Always 0
Explanation - LCS cannot exceed the length of the shorter string.
Correct answer is: Length of shorter string
Q.21 What is the base case in LCS DP table?
First row and column filled with zeros
All cells filled with one
Diagonal cells filled with one
None
Explanation - If one string is empty, the LCS is 0, so base case is zeros.
Correct answer is: First row and column filled with zeros
Q.22 Which variant of LCS is solved using suffix trees?
Longest Palindromic Subsequence
Longest Common Substring
Edit Distance
Knapsack
Explanation - Suffix trees can solve the longest common substring problem, not subsequence.
Correct answer is: Longest Common Substring
Q.23 What is the time complexity of brute force LCS?
O(m+n)
O(2^(m+n))
O(m*n)
O(m^2)
Explanation - Brute force generates all subsequences leading to exponential complexity.
Correct answer is: O(2^(m+n))
Q.24 If X='ABCD' and Y='EFGH', what is LCS length?
1
0
2
4
Explanation - There are no matching characters, hence LCS = 0.
Correct answer is: 0