Knapsack 01 DP (Practice 5027): Rehearsal
Interviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note.
Approach
dp capacity backward.
def knapsack(W,wt,val): dp=[0]*(W+1) for w,v in zip(wt,val): for c in range(W,w-1,-1): dp[c]=max(dp[c],dp[c-w]+v) return dp[W]
Complexity
Linear in the dominant input size for the scan; heap/tree variants add a log factor.
Interview pitfalls
State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.
Practicing out loud
Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see Linkjob.ai.
Further reading / Linkjob AI resource directory: directory A · directory B