Dynamic Programming Questions at Meesho: What to Expect

Dynamic Programming (DP) is a core algorithmic paradigm for optimizing complex decisions, making it highly relevant for a company like Meesho. As a social commerce platform connecting suppliers with resellers, Meesho's systems constantly solve optimization problems: minimizing delivery costs across a vast logistics network, allocating inventory efficiently, or maximizing the value of promotional offers within budget constraints. These are classic DP scenarios—problems with overlapping subproblems and optimal substructure. With 12 out of their 44 total coding questions tagged as Dynamic Programming, Meesho's interview process clearly tests a candidate's ability to model real-world resource allocation and sequencing problems into efficient, tabulated solutions. Mastering DP demonstrates you can think about scalable optimization, a critical skill for building Meesho's high-volume, cost-sensitive marketplace.

What to Expect — Types of Problems

Meesho's DP questions typically fall into two categories that mirror their business domains. First, knapsack and subset problems are prevalent, reflecting inventory bundling, budget-constrained feature development, or resource allocation. You might encounter problems like "Partition Equal Subset Sum" or "Target Sum." Second, string and sequence DP questions are common, modeling user behavior flows, transaction sequencing, or similarity matching between product catalogs. Problems like "Longest Common Subsequence," "Edit Distance," or "Longest Palindromic Subsequence" test your ability to handle state transitions in sequences. Expect the problems to be of medium to hard difficulty, often requiring you to not only implement the solution but also to explain the state definition and transition logic clearly.

How to Prepare — Study Tips with One Code Example

Start by solidifying the core principle: DP is applied recursion plus memoization. For any problem, first define the state (what parameters define a subproblem) and the recurrence relation. Practice by drawing the decision tree and identifying overlapping subproblems. Use a bottom-up tabulation approach for interview clarity, as it's often easier to explain and has better constant factors. Always be ready to discuss time and space complexity, and consider space optimization (e.g., using a 1D array instead of a 2D table).

A fundamental pattern is the 0/1 Knapsack. The core idea is that for each item, you decide to either include it or exclude it, based on capacity.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]],
                    dp[i-1][w]
                )
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

Recommended Practice Order

Build proficiency sequentially. First, master foundational 1D DP like "Climbing Stairs" and "House Robber." Next, tackle the essential 0/1 Knapsack pattern and its variants like subset sum. Then, move to 2D DP for sequences with "Longest Common Subsequence" and "Edit Distance." Finally, practice more complex problems involving intervals or state machines, such as "Best Time to Buy and Sell Stock with Cooldown." For Meesho, prioritize knapsack and string DP problems in your final review.

Practice Dynamic Programming at Meesho