CodeSignal Technical Assessment Dynamic Programming and Optimization 2 — Questions and Answers
Question 1: What space optimization reduces the LCS DP table from O(m×n) to O(min(m,n))?
- Divide and conquer split
- Using only two rows at a time (rolling array) (Correct answer)
- Pure memoization
- Recursion with stack compression
Correct answer: Using only two rows at a time (rolling array)
Since each row depends only on the previous row, storing just two rows reduces space from O(m×n) to O(n).
Question 2: In the coin change problem, what should be returned if no valid coin combination can make the target amount?
- 0
- -1 (Correct answer)
- Infinity
- null
Correct answer: -1
Returning -1 is the conventional signal that no valid combination exists for the given amount.
Question 3: What does 'optimal substructure' mean in the context of dynamic programming?
- All subproblems are the same size
- The optimal solution to the problem contains optimal solutions to its subproblems (Correct answer)
- Subproblems are solved independently without overlap
- The problem can always be solved greedily
Correct answer: The optimal solution to the problem contains optimal solutions to its subproblems
Optimal substructure means you can construct the global optimal answer by combining optimal answers to smaller subproblems.
Question 4: What is the time complexity of the standard matrix chain multiplication DP algorithm?
- O(n²)
- O(n³) (Correct answer)
- O(n log n)
- O(n!)
Correct answer: O(n³)
The matrix chain DP iterates over all chain lengths and all split points, resulting in O(n³) time complexity.
Question 5: Which DP approach builds the solution iteratively starting from the smallest subproblems?
- Memoization
- Tabulation (Correct answer)
- Recursion
- Branch and bound
Correct answer: Tabulation
Tabulation (bottom-up DP) fills a table from the base cases up, avoiding recursion entirely.
Question 6: In the 'house robber' problem, what does dp[i] typically represent?
- The index of the house to rob at step i
- The maximum money robbed from the first i houses without robbing two adjacent (Correct answer)
- The total money in all houses up to i
- The number of houses skipped up to position i
Correct answer: The maximum money robbed from the first i houses without robbing two adjacent
dp[i] holds the maximum loot achievable from the first i houses while respecting the no-adjacent constraint.
CodeSignal Technical Assessment Dynamic Programming and Optimization 2
What space optimization reduces the LCS DP table from O(m×n) to O(min(m,n))?