Dynamic Programming Interview Questions and Answers
Ques 6. 0/1 Knapsack Problem
Given weights and values of items, find the maximum value that can be obtained by selecting a subset of items with total weight not exceeding a given limit.
Example:
Weights: [2, 3, 4, 5], Values: [3, 4, 5, 6], Knapsack Capacity: 5, Output: 11
Is it helpful?
Add Comment
View Comments
Ques 7. Longest Common Subsequence (LCS)
Given two sequences, find the length of the longest subsequence present in both of them.
Example:
Input: ABCBDAB, BDCAB, Output: 4 (BCAB)
Is it helpful?
Add Comment
View Comments
Ques 8. Rod Cutting Problem
Given a rod of length n and prices at which different lengths of the rod can be sold, find the maximum value obtainable by cutting up the rod.
Example:
Lengths: [1, 2, 3, 4, 5], Prices: [1, 5, 8, 9, 10], Rod Length: 4, Output: 10
Is it helpful?
Add Comment
View Comments
Ques 9. Palindrome Partitioning
Given a string, partition it into as many palindromic substrings as possible.
Example:
Input: aab, Output: [['a', 'a', 'b'], ['aa', 'b']]
Is it helpful?
Add Comment
View Comments
Ques 10. Unique Paths
A robot is located at the top-left corner of a m x n grid. It can only move either down or right. Find the number of unique paths to reach the bottom-right corner.
Example:
Input: m = 3, n = 7, Output: 28
Is it helpful?
Add Comment
View Comments
Most helpful rated by users: