DSA interview question

Minimum Cost to Cut a Stick

Hard · Algorithms · Topics: dynamic programming, mcm, partition

The problem

You're working on an automated CNC (Computer Numerical Control) cutting machine for a furniture manufacturer. The machine needs to cut a wooden stick of length n at several specified positions to produce custom-sized pieces for a client order. Here's the catch: every cut costs money proportional to the length of the stick segment being cut (the machine charges per unit length of material it has to saw through in that pass), and the order in which you make the cuts changes which segment lengths you're cutting through at each step. Your job: given the stick's total length n and an array cuts representing the absolute positions where cuts must be made, determine the minimum total cost to perform all the cuts in some optimal order.

Example: stick of length 7, cuts at positions [1, 3, 4, 5] — the optimal cutting order yields a minimum cost of 16.

Function signature

int minCost(int n, vector<int>& cuts);

Test cases

Input `n`	Input `cuts`	Output	Explanation
7	`[1,3,4,5]`	16	Optimal order: cut at 3 first (cost 7), then 1 (cost 3), then 4 (cost 4), then 5 (cost 2) → wait, verify exact order with code; total = 16
9	`[5,6,1,4,2]`	22	Optimal cutting order minimizes total cost to 22
10	`[3]`	10	Single cut on a length-10 stick costs the full length once: 10
5	`[]`	0	No cuts to make, no cost
4	`[1,2,3]`	8	Cutting at every integer position in order 2→1→3 (or similar) minimizes cost

(Constraints typically: 2 <= n <= 10^6, 1 <= cuts.length <= min(n-1, 100), 1 <= cuts[i] <= n-1, all cuts[i] distinct)

How interviewers phrase it

"You have a stick from 0 to n. Given positions to cut at, find the minimum total cost where each cut costs the length of the piece being cut at that moment."
This is LeetCode 1547 — interviewers may frame it as a direct sequel/twin to Burst Balloons (LC 312) to test if you can recognize the same interval-DP pattern in a different costume.
Watch for the phrase "cost of a cut equals the length of the stick segment it's performed on" — this is the key mechanic that determines the recurrence.

Clarifying questions to ask

Are 0 and n themselves considered as "boundary cuts" (i.e., fixed endpoints I should think of as already-made cuts that bound every segment)? (Yes — standard trick: treat 0 and n as sentinel boundaries.)
Is the cuts array guaranteed sorted, or do I need to sort it myself first? (Usually unsorted — sorting it first is a necessary preprocessing step, important to mention.)
Can cuts contain duplicate positions, or values outside [1, n-1]? (Typically no — all distinct, strictly inside the stick — but worth confirming since it affects edge-case handling.)
What's the bound on cuts.length? (Usually ≤ 100, hinting that O(k³) where k = number of cuts is the intended complexity, NOT O(n³) since n can be up to 10^6.)

Follow-ups to expect

"How is this related to Burst Balloons?"
"Why is the complexity O(k³) and not O(n³)?"
"Can you reconstruct the actual cutting order, not just the minimum cost?"
"What if cuts could repeat or be very dense (close to n cuts)?"
"Could you solve this with a different approach, like greedy (always cut the longest segment first)?"
"Is 'first cut' or 'last cut' framing easier here, and could you use the other one?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview