Advanced DP Interview Questions and Answers: Four Worked Patterns

Advanced DP questions are rarely difficult because of syntax. The real challenge is choosing a sufficient state, justifying the transition, and combining DP with binary search, bitmasks, or tree traversal under interview pressure. An interview may stop at recognition and complexity or continue into optimisation and reconstruction; the depth varies by role and team.

1. How to recognise and answer an advanced DP question

Look for repeated subproblems, a choice whose effect survives into the future, and a compact state that makes the remaining suffix independent of the path already taken. A greedy method commits to one local choice without comparing all relevant futures. Plain backtracking explores the choice tree but repeats equivalent work.

Use this spoken sequence in an interview:

1. State the brute-force choice tree.

2. Define the state in words.

3. Write the recurrence and base cases.

4. Name the evaluation order.

5. Give time, space, and reconstruction costs.

If the state sentence is unclear, the code will usually be unclear too. For a broader programming route before these mixed patterns, use the Coding & Skills category.

2. Question 1: Weighted job scheduling with DP and binary search

Prompt: Choose non-overlapping jobs for maximum profit. Touching endpoints are compatible, so finish <= next start. The jobs, sorted by finish time, are J1=(1,3,5), J2=(2,5,6), J3=(4,6,5), J4=(6,7,4), J5=(5,8,11), and J6=(7,9,2), where each tuple is (start, finish, profit).

Let p[i] be the last job compatible with job i. With 1-based jobs and sentinel M[0]=0, binary search gives p=[0,0,1,3,2,4]. Use:

M[i] = max(M[i-1], profit[i] + M[p[i]])

The rows are:

Thus M[1..6]=[5,6,10,14,17,17]. Walking backwards skips J6, includes J5, then includes J2. The answer is J2 + J5, with profit 6 + 11 = 17.

A model answer is: sort by finish time, binary-search the last finish not greater than each start, fill the DP, then walk backwards through equalities to recover the jobs. This takes O(n log n) time including sorting and searches, and O(n) space. Sorting alone is not a greedy proof because choosing the earliest-finishing job can discard a later combination with greater total profit. Every optimal schedule over the first i jobs either excludes job i, giving M[i-1], or includes it, leaving only jobs 1 through p[i]. Those exhaustive cases justify the maximum in the recurrence.

3. Question 2: Minimum-cost assignment with bitmask DP

Prompt: Assign people P0..P3 one-to-one to jobs J0..J3. The cost rows are P0=[9,2,7,8], P1=[6,4,3,7], P2=[5,8,1,8], and P3=[7,6,9,4]. Find the minimum total cost.

Define dp[mask] as the minimum cost after assigning the first popcount(mask) people to the jobs whose bits are set. Start with dp[0000]=0. At any mask, person i=popcount(mask) tries each unset job j.

The optimal predecessor chain is 0000 (0) -> 0010 (2) -> 0011 (8) -> 0111 (9) -> 1111 (13). It represents P0->J1, P1->J0, P2->J2, and P3->J3, costing 2 + 6 + 1 + 4 = 13. A model answer states the mask meaning before the transition and stores the chosen predecessor for reconstruction.

The proof follows from the mask: it records exactly which jobs remain, so histories with the same mask have identical futures. Every one-to-one assignment appears as one path. The complexity is O(n*2^n) time and O(2^n) space, so this formulation is suitable only when n is small.

4. Question 3: Maximum-weight independent set on a tree

Prompt: Root A(5) has children B(1) and C(4). B has children D(6) and E(2), while C has child F(7). Choose maximum total weight with no parent and child both selected.

Define in[u]=weight[u]+sum(out[child]) and out[u]=sum(max(in[child],out[child])). The leaves are D=(in 6,out 0), E=(2,0), and F=(7,0). Therefore B=(1,8) and C=(4,7). At the root, A=(5+8+7, max(1,8)+max(4,7))=(20,15). The answer is 20, selecting A,D,E,F.

The proof conditions on whether u is selected, which makes its child subtrees independent. Pass a parent parameter or maintain a visited set so traversal does not return to the parent. Time is O(n), with O(n) recursion and state space.

5. Question 4: Stock trading with at most two transactions

Prompt: Prices by day are [3,2,6,5,0,3]. Complete at most k=2 buy-sell transactions, with no overlapping holdings.

Define F(day, sellsRemaining, holding) as maximum future profit. The terminal bases are F(n,t,0)=0 and F(n,t,1)=-infinity. Buying changes holding from 0 to 1. Selling changes it back to 0 and decrements sellsRemaining. For t > 0, the exact transitions are F(d,t,0)=max(F(d+1,t,0), -price[d]+F(d+1,t,1)) and F(d,t,1)=max(F(d+1,t,1), price[d]+F(d+1,t-1,0)).

The optimal trace is buy at 2, sell at 6 for 6-2=4; then buy at 0, sell at 3 for 3-0=3. Total profit is 4+3=7. Tabulation takes O(nk) time and O(k) space when previous-day and next-day arrays are kept separate.

If a fee of 2 is charged on each completed sale, subtract it in the sell transition. The same trades net (6-2-2) + (3-0-2) = 2+1=3. The added constraint changes one transition, not the whole method.

6. Follow-up questions interviewers use to test understanding

Why is your state sufficient? Any two prefixes with the same state can be merged because they offer the same legal futures. Can you return the decisions? Store parent choices, or replay comparisons in the completed recurrence. Memoisation or tabulation? Prefer memoisation when reachable states are sparse; prefer tabulation when iteration order is clear and recursion depth is risky.

Check empty input and a single job. All-decreasing prices [7,6,4,3,1] must return 0. Jobs touching at endpoints are compatible under finish <= start. Represent unreachable states with positive or negative infinity, and use a wider integer type when cost or profit sums can overflow. DSA Interview Questions by Pattern: Arrays, Trees, Graphs and Complexity covers baseline-to-structure choices for arrays, trees and unweighted graphs. Advanced DP preparation adds state sufficiency, transitions and reconstruction.

7. Common advanced-DP mistakes and how to repair them

Omitting holding from the stock state merges futures with different legal actions. Using < instead of <= for weighted jobs wrongly rejects J2->J5, since J2 finishes when J5 starts. Treating mask bits as people in one line and jobs in another corrupts assignment transitions. Updating a rolling array in the wrong direction can reuse same-day values.

Repair these errors systematically. Write the state as a sentence, list every dimension and its range, hand-trace the smallest non-trivial input, then compare one transition with brute force. J2->J5 remains compatible, and 0000->0010 assigns P0 to J1 at cost 2.

8. Short version and a focused next step

Reduce each problem to the fact its state must preserve: the last compatible job, the assigned-job mask, whether a parent is selected, or the remaining sales plus holding. Change one constraint in each problem and predict the exact state or transition that must change before touching code. Java learners can continue with DSA using Java, while Python learners can use DSA Using Python. Finish by reconstructing the chosen jobs, assignment, tree vertices and stock trades from memory; a correct value without the decisions is only half the drill.