Selling Pieces of Wood

Selling Pieces of Wood

What is this problem about?

The Selling Pieces of Wood interview question gives you a rectangular piece of wood of dimensions m × n. You can cut it horizontally or vertically into two pieces and sell pieces at given prices. Each price is specified as a (height, width, price) triple. Maximize the total revenue from selling all resulting pieces. This is a 2D dynamic programming problem on interval cutting.

Why is this asked in interviews?

Palantir Technologies asks this HARD DP problem because it models real-world resource cutting optimization — relevant in manufacturing, financial portfolio partitioning, and computational geometry. It tests the candidate's ability to formulate a 2D DP recurrence for a "cut rod" variant in two dimensions, handle the base case (an exact match in the price list), and optimize memo lookups using a hash map.

Algorithmic pattern used

The pattern is 2D memoization DP (top-down). Define dp[h][w] = maximum revenue from a piece of height h and width w. Base case: if (h, w) has a listed price, that's a starting value. Transitions: try all horizontal cuts (split h into i and h-i for all i from 1 to h//2) and all vertical cuts (split w into j and w-j). dp[h][w] = max(price[h][w], max over i of dp[i][w] + dp[h-i][w], max over j of dp[h][j] + dp[h][w-j]). Cache results to avoid recomputation.

Example explanation

Wood: 3×5. Prices: (1×4, 2), (2×2, 7), (3×1, 1), (1×3, 2), (2×1, 3).

dp[3][5]: try cutting horizontally at row 1: dp[1][5] + dp[2][5]. Try vertically at col 1: dp[3][1] + dp[3][4]. Evaluate all cuts recursively and memoize. The optimal arrangement yields maximum revenue by combining smaller pieces that match the price list.

Common mistakes candidates make

• Forgetting to include the price of selling the whole piece without cutting (base case from the price list).
• Only trying cuts up to h//2 for horizontal — symmetric cuts give the same result; this avoids redundant computation.
• Using a 2D array indexed by (h, w) but off-by-one in size — the array should be (m+1) × (n+1).
• Recomputing dp[h][w] without memoization, leading to exponential time complexity.

Interview preparation tip

For the Selling Pieces of Wood coding problem, the dynamic programming memoization interview pattern is the clean solution. This is the 2D analog of the classic "cut rod" DP problem — mention this connection to the interviewer at Palantir. Build the price lookup as a dictionary {(h, w): price} for O(1) lookup. Practice drawing the recurrence tree for a 2×3 piece to verify your transitions are correct before coding. Bottom-up DP (iterating h from 1 to m, w from 1 to n) is also valid and avoids recursion stack overhead.