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

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question