Mock 5 — Dynamic Programming (60 min)

Download and complete the starter notebook

Use the Download starter notebook button on this lesson. Open the .ipynb in JupyterLab, Jupyter Notebook, or another compatible Python 3 environment. Work in a saved copy, complete the TODOs and reflection cells, run the public checks, add the requested tests, then upload that completed .ipynb to this lesson. Do not submit a blank starter. The notebook intentionally contains no answer key or private reviewer rubric.

Instructions

You have 60 minutes. For every problem, state what each DP entry means, derive the recurrence and base case, then implement and analyze it in the notebook. You may present an optimized alternative after a clear baseline.

Problem 1 — Climbing Stairs (Easy, about 10 minutes)

Implement climb_stairs(n). From step 0, each move climbs 1 or 2 steps. Return the number of distinct ways to reach exactly step n. n is a nonnegative integer; for n=0, there is one way (take no steps).

Problem 2 — Coin Change (Medium, about 15 minutes)

Implement coin_change(coins, amount) to return the fewest coins needed to total amount, using unlimited copies of each denomination. amount >= 0; coins contains positive integers and may be empty or contain duplicates. Return -1 when no combination exists. Amount zero returns 0.

Problem 3 — Longest Increasing Subsequence (Medium, about 15 minutes)

Implement length_of_lis(nums) for a strictly increasing subsequence (elements need not be adjacent). Return its length. Empty input returns 0. Duplicate values cannot extend a strictly increasing subsequence.

Example: [10, 9, 2, 5, 3, 7, 101, 18] → 4.

Problem 4 — Word Break (Medium, about 20 minutes)

Implement word_break(s, word_dict). Return whether s can be segmented into zero or more nonempty dictionary words. The empty string is segmentable. Dictionary entries are nonempty strings; duplicates may appear. Include a test for an impossible suffix.

Examples: "leetcode", ["leet", "code"] → True; "applepenapple", ["apple", "pen"] → True; "catsandog", ["cats", "dog", "sand", "and", "cat"] → False.

Submit the completed notebook

• Download this lesson's starter Jupyter notebook, complete the requested functions, and upload the saved .ipynb file here.
• Keep your implementation, added tests, complexity reasoning, and interview reflection in the notebook. No separate source file or NOTES.md is required.
• Do not upload the untouched starter. Public checks are examples, not a complete test suite; add the edge cases requested in the notebook.
• The downloadable notebook contains no reference solutions or reviewer rubric. Notebook outputs are not used as proof of correctness; the reviewer checks your submitted source and written reasoning.