Coding

Rod cutting problem

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a rod of length N inches and an array price[] where price[i] denotes the value of a piece of rod of length i inches (1-based indexing). Determine the maximum value obtainable by cutting up the rod and selling the pieces. Make any number of cuts, or none at all, and sell the resulting pieces.

Input: price = [1, 6, 8, 9, 10, 19, 7, 20], N = 8 Output: 25 Explanation: Cut the rod into lengths of 2 and 6 for a total price of 6 + 19= 25.

Input: price = [1, 5, 8, 9], N = 4 Output: 10 Explanation: Cut the rod into lengths of 2 and 2 for a total price of 5 + 5 = 10.

Input: price = [5, 5, 8, 9, 10, 17, 17, 20], N = 8

1 ≤ N ≤ 1000
1 ≤ price[i] ≤ 105

cpp

class Solution{
  public:
    int rodCutting(vector<int> price, int n) {
     
    }
};

java

class Solution{
    public int RodCutting(int price[], int n) {
    }
}

python

class Solution:
    def RodCutting(self, price, n):

javascript

class Solution {
    RodCutting(price, n) {
       
    }
}

csharp

class Solution
{
    public int RodCutting(int[] price, int n)
    {
    }
}

func RodCutting(price []int, n int) int {
	
}

Stuck? Show a way to structure it+

01Let dp[len] be the best revenue for a rod of length len.
02For every allowed piece length, consider taking it plus dp of the remainder.
03Allow reusing the same piece length.
04Return dp[N].

Reference answer

A rod of length len can start with any first cut cut from 1 through len, then earn price[cut-1] + dp[len-cut]. Thus dp[len]=max(price[cut-1]+dp[len-cut]). Fill lengths from 1 to N, or view each piece length as an unbounded-knapsack item and update capacities upward. Both formulations are O(N^2) time and O(N) space. Reuse is allowed, so a 0/1 loop order is incorrect. The option of no cut is automatically included by choosing a piece of length len. To explain correctness, take an optimal decomposition of length len: its first piece has some legal length cut, and the remaining rod must itself have optimal revenue or the whole decomposition could be improved. Conversely, every recurrence choice yields a legal cut plan. Keep a choice[len] array only if the interviewer asks for the actual decomposition, not just its value.

Then expect these follow-ups

How would you return the actual cut lengths?
Tests: DP reconstruction
Why is this equivalent to unbounded knapsack?
Tests: problem reduction

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question