Question 1
How do you efficiently check if an array contains a duplicate in O(n) time complexity?
1
Sort and check adjacent elements
2
Use a nested loop
3
Use a hash set
4
Use a binary search
Question 2
which algorithm would you use to solve a maze problem?
1
Bubble sort
2
Binary search
3
Depth-first search
4
Linear search
Question 3
Which of the following is not a necessary property for a problem to be solved effectively by dynamic programming?
1
Greedy choice property
2
A recursive or tabulated formulation
3
Overlapping subproblems
4
Optimal substructure
Question 4
In the bottom‐up tabulation approach to dynamic programming, which of the following is typically the correct order of steps?
1
Declare table → fill table arbitrarily → define recurrence → answer
2
Write naive recursion → identify overlapping subproblems → memorize → convert to tabulation
3
Identify recurrence → choose memorization → fill table → return result
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(ϕ^n) (approx exponential)
2
O(log n)
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(m+n)
2
O(2^(m+n))
3
O(m*n)
4
O(max(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
Huffman Coding
2
Activity Selection
3
Fractional Knapsack
4
0/1 Knapsack
Question 8
Which of the following best describes memorization in dynamic programming?
1
Storing results of subproblems to avoid recomputation
2
Greedy selection of the best immediate choice
3
Dividing the problem into independent subproblems
4
Filling a table iteratively bottom‐up