Question
Consider the standard dynamic programming approach to find the length of the Longest Common Subsequence (LC
- S of two strings, text1 and text2. The dp table is initialized with dimensions (len(text1) + 1) x (len(text2) + 1). Given text1 = "ABC" and text2 = "AXBY", what will be the value of dp[0][3] and dp[2][0] after the initialization and the first row/column filling steps of the following Python code? def lcs_length(text1, text2): m = len(text1) n = len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] # Initialization (first row and column are already 0 by default in Python list comprehension) # for i in range(m + 1): # dp[i][0] = 0 # for j in range(n + 1): # dp[0][j] = 0 # Filling the DP table for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n] # For this question, we only care about the state after initialization # and before the main loops start filling values beyond the first row/column. # The Python list comprehension [[0] * (n + 1) for _ in range(m + 1)] # already initializes all cells to 0.
More Data Structure Questions
- Using Kruskal's algorithm on a graph with edges A-B(1), B-C(3), A-C(4), C-D(2), B-D(5), what is the total weight of the Minimum Spanning Tree?
- What is the worst-case time to decrease a key in a binary min-heap?
- Which cryptographic concept ensures that data integrity is preserved and cannot be altered during transmission?
- In a hash table, what is a 'collision'?
- Using the Master Theorem, what is the time complexity of the recurrence T(n) = 3T(n/2) + n²?
- Which memory type is the fastest but most expensive, typically located directly on the CPU?
- Which of the following attacks can occur when a user is tricked into performing unintended actions on a trusted website without their knowledge?
- Which of the following integrity constraints ensures that every non-null foreign key value must reference an existing primary key value in another table?
- For T(n)=2T(n/2)+n, which bound follows from the Master Theorem?
- What is the height of a balanced binary tree containing n nodes, expressed in Big-O notation?
Hey! Ask a query
Please enter email id
The email must be a valid email address.
Please enter Mobile Number
Please enter valid Mobile Number
Please enter your Doubt
Think You're Ready for RBI Grade B?
RBI Grade B 2026 Phase 1 Memory Based Paper
- 200 Questions with Detailed Solutions
- Section-wise Coverage (GA, English, Quant & Reasoning)