DSA interview question

Rod Cutting Problem

Hard · Algorithms · Topics: dynamic programming, unbounded knapsack

The problem

You're consulting for a metal-fabrication company that buys rods of raw steel and cuts them into smaller pieces to sell. Each possible piece length has its own market price (longer isn't always proportionally more valuable — market demand varies oddly by length). Given a rod of length N and a price[] array where price[i] is the price of a piece of length i+1, determine the maximum total value obtainable by cutting the rod into pieces (including the option of not cutting it at all) and selling each piece. You can cut the rod into any number of pieces of any lengths, and each length can be reused as many times as needed (e.g., you could cut a length-8 rod into eight length-1 pieces if that's most profitable).

Function signature

int rodCutting(vector<int>& price, int N);

Test cases

`price` (1-indexed by length)	`N`	Output	Explanation
`[1,5,8,9,10,17,17,20]`	8	22	cut into lengths 2+6 → 5+17 = 22
`[2,5,7,8]`	4	10	cut into two pieces of length 2 → 5+5 = 10
`[3,5,8,9,10,17,17,20]`	8	24	cut into length 2 pieces four times → 5*4=20... verify via code
`[1,5,8,9]`	1	1	rod of length 1, only option is to sell as-is
`[]`	0	0	zero-length rod, no value
`[5,8,2,4]`	4	10	sometimes not cutting at all (selling full length 4 for its own price) can lose to cutting into two length-1s (5+5=10)

(Always verify: price array is 1-indexed conceptually — price[0] is the price for length-1 piece. Confirm array indexing convention with interviewer.)

How interviewers phrase it

"Given a rod of length N and a price table for each possible cut length, maximize total revenue from cutting and selling pieces."
"You have a rod, you can cut it anywhere, each length sells for a given price — what's the max money you can make?"
Sometimes phrased without the "rod" framing at all — e.g., "given a budget N and item values per unit size, maximize value" — this is a disguised unbounded knapsack.

Clarifying questions to ask

Can each cut-length be used multiple times (i.e., can I cut two pieces of the same length)? — Confirm this is unbounded, not a 0/1 selection, since that changes the DP category entirely.
Is price[] 1-indexed by length (price[0] = price for length 1) or does it include price for length 0?
Is "no cutting at all" (selling the whole rod as one piece) a valid option? (Yes, by default — it's captured by price[N-1] being one of the choices.)
Are prices guaranteed non-negative? Could cutting ever be disadvantageous (i.e., is price[] guaranteed non-decreasing)? — If not guaranteed monotonic, that's exactly why the general DP (not a greedy) is needed.
What's the expected range of N? (Signals whether O(N²) DP is fine, or if a smarter approach is expected — usually O(N²) is the expected optimal here.)

Follow-ups to expect

"How is this related to the Unbounded Knapsack problem?"
"Can you optimize space?"
"Can you also return which cuts were made, not just the max value?"
"What if there's a fixed cost per cut (e.g., each cut costs you money for labor)?"
"What if you can only make at most K cuts total?"
"Compare this to the classic 0/1 Knapsack you may have solved before."

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