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 algorithm solves the Longest Increasing Subsequence in O(n log n) time?
Answer: Binary search with patience sorting
Using binary search to maintain a sorted 'pile' structure (patience sorting) achieves O(n log n) for LIS.
Why can't a greedy ratio (value/weight) approach always find the optimal solution for 0/1 knapsack?
Answer: Items cannot be fractionally selected, so the highest-ratio item may waste capacity
In 0/1 knapsack, items are taken whole, so a high-ratio item might leave unusable capacity that smaller items could fill better.
What does 'overlapping subproblems' mean in dynamic programming?
Answer: The same subproblems recur multiple times during the recursive computation
Overlapping subproblems occur when naïve recursion solves the same subproblem repeatedly, which DP avoids by caching.
In the edit distance DP table, what operation does a diagonal move represent when the characters at positions i and j differ?
Answer: Substitution
A diagonal transition with differing characters adds 1 for the substitution operation, replacing one character with another.
What is the recurrence for the classic 0/1 knapsack DP when item i has weight w[i] and value v[i]?
Answer: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) if c >= w[i]
For each item you choose the best of skipping it (dp[i-1][c]) or taking it (dp[i-1][c-w[i]]+v[i]) when capacity allows.
Which of the following is the correct time complexity of a simple recursive Fibonacci solution without memoization?
Answer: O(2^n)
Without memoization, each call branches into two recursive calls, resulting in an exponential O(2^n) call tree.