Interview Questions on Dynamic Programming (C Language)

📘 Basic DP Concepts – Short Answer Interview Questions

  1. What is Dynamic Programming?
    A method for solving complex problems by breaking them into simpler subproblems and storing their solutions.
  2. What are the two main approaches in DP?
    Memoization (top-down) and Tabulation (bottom-up).
  3. What are the characteristics of problems suitable for DP?
    Optimal substructure and overlapping subproblems.
  4. What is the difference between DP and Divide and Conquer?
    DP stores solutions to overlapping subproblems while Divide and Conquer doesn't.
  5. How do you identify a DP problem?
    Look for problems asking for optimal solutions with recursive structure and repeated calculations.
  6. What is memoization in DP?
    Storing results of expensive function calls and reusing them when same inputs occur again.
  7. What is tabulation in DP?
    Building a table (usually array) to store solutions to subproblems in bottom-up manner.
  8. What is the time complexity of Fibonacci using DP?
    O(n) with DP, compared to O(2^n) with naive recursion.
  9. How do you implement memoization in C?
    Use a global array or hash table to store computed results.
  10. What is the space complexity of DP solutions?
    Typically O(n) for 1D problems, O(n^2) for 2D problems, but can often be optimized.
  11. What is optimal substructure property?
    Optimal solution can be constructed from optimal solutions of subproblems.
  12. What are overlapping subproblems?
    When a problem can be broken into subproblems which are reused several times.
  13. How do you convert a recursive solution to DP?
    Add memoization or rewrite as iterative solution with table.
  14. What is the difference between DP and greedy algorithms?
    DP considers all possibilities while greedy makes locally optimal choices.
  15. How do you handle DP problems with constraints?
    Add constraints as additional dimensions to the DP table.
  16. What is state in DP?
    The set of parameters that define a subproblem.
  17. How do you determine the DP table dimensions?
    Based on the number of parameters needed to uniquely identify subproblems.
  18. What is the knapsack problem?
    Select items with given weights and values to maximize value without exceeding weight capacity.
  19. What are common DP patterns?
    0/1 Knapsack, Unbounded Knapsack, Fibonacci, LCS, LIS, Matrix Chain Multiplication, etc.
  20. How do you optimize DP space complexity?
    Use rolling arrays or only store necessary previous states.
  21. What is the time complexity of 0/1 Knapsack?
    O(nW) where n is number of items and W is capacity.
  22. How do you reconstruct the solution in DP?
    Store parent pointers or backtrack through the DP table.
  23. What is the longest common subsequence problem?
    Find the longest sequence that appears in both strings in order but not necessarily contiguous.
  24. What is the longest increasing subsequence problem?
    Find the longest subsequence where elements are in increasing order.
  25. How do you handle DP problems with cyclic dependencies?
    Restructure the problem or use memoization with cycle detection.
  26. What is the matrix chain multiplication problem?
    Find the optimal way to parenthesize matrix multiplication to minimize operations.
  27. What's the difference between top-down and bottom-up DP?
    Top-down is recursive with memoization, bottom-up is iterative building up solutions.
  28. How do you initialize a DP table?
    Set base cases and initialize other values appropriately (often 0 or INT_MAX).
  29. What is the coin change problem?
    Find minimum number of coins needed to make a given amount.
  30. How do you handle DP problems with multiple constraints?
    Add each constraint as a dimension to the DP table.

📗 Advanced DP Problems – Short Answer Interview Questions

  1. How do you solve the edit distance problem?
    Use DP table where dp[i][j] represents operations needed to convert first i chars of str1 to first j chars of str2.
  2. What is the optimal binary search tree problem?
    Arrange keys in BST to minimize expected search cost given access frequencies.
  3. How do you solve the weighted interval scheduling problem?
    Sort by finish time, use DP to select non-overlapping intervals with max weight.
  4. What is the Floyd-Warshall algorithm?
    DP algorithm to find shortest paths between all pairs of vertices in a weighted graph.
  5. How do you solve the traveling salesman problem with DP?
    Use Held-Karp algorithm with DP table representing subsets of cities.
  6. What is the Bellman-Ford algorithm?
    DP algorithm to find shortest paths from single source, can handle negative weights.
  7. How do you implement DP for problems with large constraints?
    Use memoization with maps instead of arrays or optimize state representation.
  8. What is the rod cutting problem?
    Find optimal way to cut rod into pieces to maximize profit given price for each length.
  9. How do you solve the subset sum problem?
    DP table where dp[i][j] is true if subset of first i elements sums to j.
  10. What is the egg dropping problem?
    Find minimum trials needed to determine critical floor where eggs break.
  11. How do you solve the palindrome partitioning problem?
    DP to find minimum cuts needed to partition string into palindromic substrings.
  12. What is the maximum subarray problem?
    Find contiguous subarray with largest sum (Kadane's algorithm).
  13. How do you solve the boolean parenthesization problem?
    DP to count number of ways to parenthesize boolean expression to evaluate to true.
  14. What is the longest palindromic subsequence problem?
    Find longest subsequence that reads the same forwards and backwards.
  15. How do you solve the word break problem?
    DP where dp[i] is true if first i characters can be segmented into dictionary words.
  16. What is the stock buy/sell problem with at most k transactions?
    DP table where dp[t][d] represents max profit with t transactions up to day d.
  17. How do you solve the maximum product subarray problem?
    Track both max and min product at each step due to negative numbers.
  18. What is the counting DP approach?
    DP where we count number of ways to achieve something rather than find optimal value.
  19. How do you solve the dice throw problem?
    Count number of ways to get sum X with N dice, each having M faces.
  20. What are common DP optimizations?
    Space optimization, state reduction, precomputation, mathematical insights.
Related DP Resources
Basic Programs
MCQs
Problem Solving Tricks
Tech Hub