Question 1
Which of the following problems can be solved using Dynamic Programming?
1
Finding the largest prime number
2
Finding the root of a polynomial equation
3
Finding the factorial of a number
4
Solving the Fibonacci sequence
Question 2
Which of the following problems can be solved efficiently using the Kadane’s Algorithm?
1
Merging two arrays
2
Sorting an array
3
Searching for an element
4
Finding the maximum subarray sum
Question 3
Which of the following is not a necessary property for a problem to be solved effectively by dynamic programming?
1
Optimal substructure
2
Greedy choice property
3
A recursive or tabulated formulation
4
Overlapping subproblems
Question 4
In the bottom‐up tabulation approach to dynamic programming, which of the following is typically the correct order of steps?
1
Write naive recursion → identify overlapping subproblems → memorize → convert to tabulation
2
Identify recurrence → choose memorization → fill table → return result
3
Declare table → fill table arbitrarily → define recurrence → answer
4
Define DP state → write recurrence → choose iteration order → fill table → return answer
Question 5
Consider a code for the problem of computing the nth Fibonacci number using dynamic programming (either memoization or tabulation). What is the time complexity of the optimal DP solution?
1
O(log n)
2
O(ϕ^n) (approx exponential)
3
O(n)
4
O(n²)
Question 6
The problem: “Given two sequences X and Y of lengths m and n, find the length of their Longest Common Subsequence (LCS)”. What is the typical time complexity of the standard DP solution?
1
O(max(m,n)²)
2
O(2^(m+n))
3
O(m+n)
4
O(m*n)
Question 7
In the context of coding interview problems, which of the following is least likely to be solved by a pure greedy algorithm and more likely to require dynamic programming?
1
Fractional Knapsack
2
Huffman Coding
3
0/1 Knapsack
4
Activity Selection
Question 8
Which of the following best describes memorization in dynamic programming?
1
Greedy selection of the best immediate choice
2
Dividing the problem into independent subproblems
3
Storing results of subproblems to avoid recomputation
4
Filling a table iteratively bottom‐up