Skip to content
Tech Interview Prep
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 Q&A
25
Edition
v7
Editorial status
Reviewed

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

Curated: · Written: · Reviewed:

25 questions

MCQ-3A 1-D DP computes L[i], the length of the longest increasing subsequence starting at index i, with L[i] = 1 + max{L[j] : j > i and a[j] > a[i]} when such j exist, and L[i] = 1 otherwise. Every read targets an index greater than i. Which property makes this recurrence valid for dynamic programming?
MCQ-2A teammate argues that a 1-D DP is unsound in general: "dp[i] is a single number, but the optimal solution can reach position i through many different histories, and those histories constrain what you may do next." Which reply states the condition under which one value per index is nevertheless a correct state?
MCQ-7A Python module defines `@cache def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)`. In one process, a test calls `fib(35)` and then `fib(36)`. How many times does the function body execute across both calls?
MCQ-8A team implements the Climbing Stairs count (1 or 2 steps per move) with a 1-indexed array dp[1..n]: step 0 is the ground and is never stored, so the recurrence can only be evaluated at indices whose two predecessors both exist. Which formulation returns the correct number of distinct paths for every n ≥ 1?
MCQ-23A team implements a DP for the maximum sum of non-adjacent elements in an array: `dp[0] = a[0]`, `dp[1] = a[1]`, and `dp[i] = max(dp[i-1], dp[i-2] + a[i])` for `i >= 2`. It passes every provided example. A randomised comparison against a brute-force reference on arrays of length up to 8 finds the first mismatch on `[2, 1, 4, 9]`: the DP returns 10, brute force returns 11. Which single change makes the DP agree with brute force on this input and on the rest of the small-input sweep?
MCQ-9A candidate implements the house-robber recurrence with a single running variable: ```python best = 0 for i, v in enumerate(a): best = max(best, (a[i-2] if i >= 2 else 0) + v) return best ``` For `a = [2, 7, 9, 3, 1]`, what does this return?
MCQ-12A payments service must count the distinct multisets of coins that sum to 7 using denominations [1, 2, 5]; the order of coins in the sequence does not matter. An engineer writes: dp = [0] * 8 dp[0] = 1 for amt in range(1, 8): for c in [1, 2, 5]: if c <= amt: dp[amt] += dp[amt - c] What does this code return for target 7, and what does swapping the loops to coins outer return?
MCQ-6A 0/1 knapsack DP keeps a one-dimensional table dp[c] over capacities c = 0..4, with the item loop outer and the capacity loop inner, and dp initialised to 0. The items are (weight 2, value 5) and (weight 3, value 6). The inner loop runs c from the item's weight up to 4. What value does dp[4] hold when the run finishes?
MCQ-13A 1-D knapsack DP uses `dp[w] = max(dp[w], dp[w - weight] + value)` and loops `w` from `capacity` down to `weight`. A test where taking one item twice would improve the result still returns the 0/1 optimum. Which change makes the same recurrence allow unlimited copies of each item?
MCQ-4A packing service fills each bin exactly to capacity C. Items are unlimited, each with a weight and a value, and the service reports the largest total value that fills a bin exactly, or -1 when no exact fill exists. The dynamic program, in Python 3: ```python def best(items, C): dp = [0] * (C + 1) # line under review for c in range(1, C + 1): for w, v in items: if w <= c: dp[c] = max(dp[c], dp[c - w] + v) return dp[C] ``` For items = [(2, 5)] and C = 3, what does this function return, and why?
MCQ-10While reviewing a Kadane's algorithm implementation for the Maximum Subarray problem, a colleague asks why the loop maintains a separate variable for the maximum sum ending at the current index rather than updating only the overall maximum. Which statement describes the two states correctly?
MCQ-11A candidate proposes a one-pass recurrence for the maximum-subarray sum and tests it on [2, -1, 3, -4, 2] and on [-3, -1, -7]. Which formulation returns the correct answer on both?
MCQ-1A team memoises `f(i)`, the maximum sum of a subsequence of `a[i:]` with no two chosen elements adjacent, using `f(i) = max(a[i] + f(i+2), f(i+1))` and `f(n) = 0`, with the memo table keyed on `i`. They add a requirement that the chosen subsequence must have even length, but keep the recurrence and the key unchanged. For `a = [3, 1, 4, 1, 5]`, the memoised `f(0)` returns 12, while the true optimum under the even-length requirement is 9. What is the cause?
MCQ-22A vending machine returns change with as few coins as it can, using 1-, 3- and 4-cent coins. Its loop repeatedly takes the largest coin that still fits; asked for 6 cents it returns 4+1+1. An engineer proposes replacing the loop with a dynamic program. Which statement about the two approaches on this input is correct?
MCQ-25Three weighted intervals are given, half-open so that [0,4) and [4,8) do not overlap: A = [0,4) with weight 5, B = [1,3) with weight 1, C = [4,8) with weight 5. A colleague proposes the greedy rule 'repeatedly take the compatible interval that finishes earliest' and claims it is optimal for this instance. Which statement about the instance is correct?
MCQ-14A service computes edit distance between two 10,000-character strings using a full (m+1)×(n+1) table of 32-bit ints, about 400 MB, and the job is killed by a 256 MB memory limit. The team rewrites it to keep a single row of n+1 ints. Which statement about the rewrite is correct?
MCQ-15A service solves 0/1 knapsack for capacity 3 with items A=(weight 1, value 2), C=(weight 2, value 4), and B=(weight 1, value 3), processed in that order. It keeps only the final one-row DP array, which is [0, 3, 5, 7]. A new requirement asks for the chosen item indices. An engineer proposes walking backward through this final array: for each item in reverse order, if dp[c] == dp[c - weight] + value, take it and set c -= weight. What does that return, and what should they do instead?
MCQ-16A batch job computes the longest strictly increasing subsequence of 10^6 timestamps. The current O(n²) DP takes 42 s per batch against a 5 s SLA. An engineer swaps in the patience-sorting loop that keeps a tails array and calls bisect.bisect_left(tails, v) for each value, returning len(tails); the batch now runs in about 0.5 s and reports 812. A downstream report needs the 812 timestamps themselves, in order. What is the correct assessment?
MCQ-17A DP over intervals of an array of length n = 500 fills dp[i][j] = min over k in [i, j) of dp[i][k] + dp[k+1][j] + w(i, j). Profiling shows the fill takes 0.4 s. The team then needs dp[i][j][c] for c in 0..19, keeping the same min over k. What runtime should they budget for the extended fill?
MCQ-18A payments team splits a batch of invoices into two groups of equal total value using a subset-sum DP whose table has n·S cells, where n is the invoice count and S is the total value in cents. Today's batch is n = 500 invoices with S = 2,000,000 cents, and the run takes 4 seconds. Tomorrow's batch has 1,000 invoices drawn from the same value distribution, so S = 4,000,000 cents. What should they expect for tomorrow's run?
MCQ-19A retry-budget planner memoizes a DP over (position, budget, mode): position 0..4095, budget 0..255, mode 3 values, 8-byte cells. The table must be fully resident in a 64 MiB container. A teammate adds a fourth axis, last-used key (32 values), because the recurrence is wrong without it. The recurrence for position i reads only position i-1; the budget, mode and key axes are read at the current position, not carried across positions. Which table fits the limit?
MCQ-5A batch job computes f(i) = max(f(i-1), f(i-2) + a[i]) for i in [0, 500000), where a is a 500,000-element float64 array (4 MB) held in memory. The job must return the complete f array (all 500,000 float64 values) to the caller, which reads it after the job exits. The container caps the job's resident memory at 10 MB for a, the returned f, and any DP scratch state. CPython's default recursion limit is 1,000. Which implementation fits the cap?
MCQ-21A top-down memoized solution for minimum path sum on a 3000 × 3000 grid uses dp(i, j) = grid[i][j] + min(dp(i+1, j), dp(i, j+1)), with dp(2999, 2999) = grid[2999][2999]. Run in CPython with its default recursion limit of 1000, the first call dp(0, 0) raises RecursionError. Which statement explains the depth and the fix?
MCQ-20A pricing service keeps one live `Pricing` object per region. `total` is memoised: ```python from functools import lru_cache class Pricing: def __init__(self, tax_rate): self.tax_rate = tax_rate @lru_cache(maxsize=None) def total(self, subtotal): return round(subtotal * (1 + self.tax_rate), 2) ``` A config watcher updates the live object with `pricing.tax_rate = 0.20` when the rate changes. `pricing.total(100)` returned 119.0 before the change and still returns 119.0 after it, though 120.0 is expected. What explains the stale result?
MCQ-24A counting DP keeps each count modulo 1_000_000_007 in Java int fields, and one transition triples the previous count. When the loop reaches index i, dp[i - 1] holds 1_000_000_000, and the line that runs is `dp[i] = (dp[i - 1] * 3) % MOD;` with `static final int MOD = 1_000_000_007;` (Java 17). What does dp[i] hold after that line?