CodeSignal Technical Assessment Dynamic Programming and Optimization

Question 1

What is the time complexity of solving the 0/1 knapsack problem with n items and capacity W using dynamic programming?

Accepted Answer

O(nW)

Answer

O(n + W)

Answer

O(n²)

Answer

O(2^n)

Question 2

Which dynamic programming strategy works top-down by caching results of already-solved subproblems?

Accepted Answer

Memoization

Answer

Tabulation

Answer

Greedy

Answer

Backtracking

Question 3

What two properties must a problem have to be solvable with dynamic programming?

Accepted Answer

Optimal substructure and overlapping subproblems

Answer

Sorted input and unique solution

Answer

Linear time and constant space

Answer

Greedy choice and independence

Question 4

In the Longest Common Subsequence problem, what does dp[i][j] represent?

Accepted Answer

Length of LCS of the first i chars of s1 and first j chars of s2

Answer

Length of the common prefix

Answer

Number of matching characters at positions i and j

Answer

Index of the last common character

Question 5

What are the base case values for dp[0][j] and dp[i][0] in the edit distance problem?

Accepted Answer

dp[0][j] = j and dp[i][0] = i

Answer

Both are 0

Answer

Both are 1

Answer

Depends on string content

Question 6

Kadane's algorithm solves which classic dynamic programming problem in O(n) time?

Accepted Answer

Maximum Subarray Sum

Answer

Longest Common Subsequence

Answer

Edit Distance

Answer

0/1 Knapsack