CodeSignal Technical Assessment Dynamic Programming and Optimization 1 ā Questions and Answers
Question 1: What is the time complexity of solving the 0/1 knapsack problem with n items and capacity W using dynamic programming?
- O(n + W)
- O(nW) (Correct answer)
- O(nĀ²)
- O(2^n)
Correct answer: O(nW)
The 0/1 knapsack DP fills a table of size n Ć W, giving O(nW) time complexity.
Question 2: Which dynamic programming strategy works top-down by caching results of already-solved subproblems?
- Tabulation
- Memoization (Correct answer)
- Greedy
- Backtracking
Correct answer: Memoization
Memoization is a top-down technique that stores previously computed results to avoid redundant calculations.
Question 3: What two properties must a problem have to be solvable with dynamic programming?
- Sorted input and unique solution
- Optimal substructure and overlapping subproblems (Correct answer)
- Linear time and constant space
- Greedy choice and independence
Correct answer: Optimal substructure and overlapping subproblems
DP requires optimal substructure (optimal solution uses optimal sub-solutions) and overlapping subproblems (same subproblems recur).
Question 4: In the Longest Common Subsequence problem, what does dp[i][j] represent?
- Length of the common prefix
- Length of LCS of the first i chars of s1 and first j chars of s2 (Correct answer)
- Number of matching characters at positions i and j
- Index of the last common character
Correct answer: Length of LCS of the first i chars of s1 and first j chars of s2
dp[i][j] stores the length of the LCS considering only the first i characters of s1 and the first j characters of s2.
Question 5: What are the base case values for dp[0][j] and dp[i][0] in the edit distance problem?
- Both are 0
- dp[0][j] = j and dp[i][0] = i (Correct answer)
- Both are 1
- Depends on string content
Correct answer: dp[0][j] = j and dp[i][0] = i
Converting an empty string to a length-j string requires j insertions, and converting length-i to empty requires i deletions.
Question 6: Kadane's algorithm solves which classic dynamic programming problem in O(n) time?
- Longest Common Subsequence
- Maximum Subarray Sum (Correct answer)
- Edit Distance
- 0/1 Knapsack
Correct answer: Maximum Subarray Sum
Kadane's algorithm finds the contiguous subarray with the largest sum by tracking the current and global maximum in a single pass.
CodeSignal Technical Assessment Dynamic Programming and Optimization 1
What is the time complexity of solving the 0/1 knapsack problem with n items and capacity W using dynamic programming?