Dynamic Programming and Optimization Flashcards
6 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Dynamic Programming and Optimization flashcards as text
What space optimization reduces the LCS DP table from O(m×n) to O(min(m,n))?
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).
In the coin change problem, what should be returned if no valid coin combination can make the target amount?
Answer: -1
Returning -1 is the conventional signal that no valid combination exists for the given amount.
What does 'optimal substructure' mean in the context of dynamic programming?
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.
What is the time complexity of the standard matrix chain multiplication DP algorithm?
Answer: O(n³)
The matrix chain DP iterates over all chain lengths and all split points, resulting in O(n³) time complexity.
Which DP approach builds the solution iteratively starting from the smallest subproblems?
Answer: Tabulation
Tabulation (bottom-up DP) fills a table from the base cases up, avoiding recursion entirely.
In the 'house robber' problem, what does dp[i] typically represent?
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.