Technical interview guide

1-D Dynamic Programming

Breaking a problem into overlapping subproblems indexed by a single variable, solved once each and reused.

Read: 44 min
Practice MCQs: 25
Interview QA: 25
Edition: v7
Editorial status: Reviewed
Relevant for: AI EngineerBackend EngineerBlockchain DeveloperComputational BiologistData ScientistEmbedded Systems EngineerFrontend EngineerFull-Stack DeveloperMachine Learning EngineerQuantum Software EngineerRobotics EngineerSoftware Engineer

Scope: Language-neutral, with memoisation and recursion behaviour cited from CPython 3.14.

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-05 · Written: 2026-10-05 · Reviewed: 2026-10-03

QA-1

Explain the two conditions for dynamic programming and how it changes a production decision.

QA-2

How would you reason about defining the state in a system you own?

QA-3

Walk through the transition, including where engineers most often get it wrong.

QA-4

What does base cases guarantee, and what does it deliberately leave open?

QA-5

Describe memoisation versus tabulation and the evidence you would collect before relying on it.

QA-6

A teammate proposes a design that hinges on the iteration order in tabulation. How do you evaluate it?

QA-7

Where does the Fibonacci example and its lesson matter, and where is it irrelevant?

QA-8

Teach climbing stairs and counting paths to an engineer who has only seen it as a rule of thumb.

QA-9

How do you formulate the recurrence relation and space-optimized state transition for the House Robber problem?

QA-10

How would you test a claim that the system depends on ending-here versus best-so-far?

QA-11

How does Kadane's algorithm solve the maximum subarray problem in O(n) time and O(1) space, and how do you handle arrays where all elements are negative?

QA-12

How do you formulate the recurrence relation for the Coin Change problem (fewest coins to make up an amount), and what is its time and space complexity?

QA-13

What is the difference in state transition and inner loop iteration order between 0/1 knapsack and unbounded knapsack in a 1-D array?

QA-14

When would you refuse a design because of space optimisation by rolling arrays?

QA-15

How do you reconstruct the optimal sequence of choices in a 1-D DP problem rather than just computing the optimal value?

QA-16

What failure would you inject to check a team's understanding of longest increasing subsequence?

QA-17

How should on-call treat an alert that names the complexity of a dynamic program as the cause?

QA-18

What belongs in a runbook section on pseudo-polynomial complexity, and what does not?

QA-19

How would you review a pull request whose risk is state-space explosion?

QA-20

What trade-off does cache keys and hashability force that a junior answer usually skips?

QA-21

How would you brief product on why recursion limits in top-down solutions delays a ship date?

QA-22

What is the smallest experiment that would change your mind about greedy versus dynamic programming?

QA-23

How does verifying against brute force interact with rollback, and where do people ignore that?

QA-24

What would you ask a candidate who recites numeric overflow in counting problems but cannot apply it?

QA-25