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 is the time complexity of solving the 0/1 knapsack problem with n items and capacity W using dynamic programming?
Answer: O(nW)
The 0/1 knapsack DP fills a table of size n × W, giving O(nW) time complexity.
Which dynamic programming strategy works top-down by caching results of already-solved subproblems?
Answer: Memoization
Memoization is a top-down technique that stores previously computed results to avoid redundant calculations.
What two properties must a problem have to be solvable with dynamic programming?
Answer: Optimal substructure and overlapping subproblems
DP requires optimal substructure (optimal solution uses optimal sub-solutions) and overlapping subproblems (same subproblems recur).
In the Longest Common Subsequence problem, what does dp[i][j] represent?
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.
What are the base case values for dp[0][j] and dp[i][0] in the edit distance problem?
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.
Kadane's algorithm solves which classic dynamic programming problem in O(n) time?
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.