Coding

2d dynamic Programming question

Asked at

Infosys

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Ask for the exact input, output, constraints, and allowed moves/actions.
02Propose defining a 2D state only after the objective is known.
03Confirm base cases and transition dependencies.
04State that no correct implementation can be selected from the current prompt alone.

Reference answer

This record contains only a topic label, not a solvable problem. A strong interview response is to clarify the objective: what do the two dimensions represent, what are the inputs, which moves or choices are allowed, what must be optimized or counted, and what are the constraints? Once those are known, define dp[i][j] in one sentence, list its base cases, derive transitions from smaller states, and verify iteration order respects dependencies. Do not present a specific recurrence such as LCS, grid paths, or knapsack as though it were implied: those are different 2D-DP problems with incompatible contracts.

Complexity: For an R by C state table with constant transitions, the standard bound is O(RC) time and O(RC) space, often reducible to O(C) rolling storage.

Then expect these follow-ups

Can you provide the inputs, objective, and permitted transitions?
Tests: requirements gathering
How do you decide whether a problem needs 1D or 2D DP?
Tests: state modeling

Hiring now

Get the Infosys interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question