Filling Bookcase Shelves

Filling Bookcase Shelves

What is this problem about?

The Filling Bookcase Shelves interview question asks you to arrange a sequence of books on shelves of a fixed width. For each book, you are given its thickness and its height. You must place books in the order they are given. You can start a new shelf at any time, but the total thickness of books on a single shelf cannot exceed the shelfWidth. The height of a shelf is determined by the tallest book on it. Your goal is to minimize the total height of the bookcase (the sum of heights of all shelves).

Why is this asked in interviews?

Companies like Google and Amazon use this Dynamic Programming interview pattern to test your ability to make optimal grouping decisions. It's a variation of the "Partition problem" or "Word Wrap" algorithm. It evaluates if you can identify that the decision of where to split the current shelf depends on the optimal arrangement of the previous books.

Algorithmic pattern used

The problem is solved using 1D Dynamic Programming.

1. Define dp[i] as the minimum height to arrange the first i books.
2. Base case: dp[0] = 0.
3. Transition: To find dp[i], try placing the $i^{th}$ book on a new shelf with some number of preceding books ($i-1, i-2...$).
   • dp[i] = min(dp[j] + max_height_of_books_from_j_to_i) where the sum of thicknesses from $j$ to $i$ is $\le ext{shelfWidth}$.
4. The result is dp[n].

Example explanation

Books: [[1, 2], [2, 3], [2, 3]], shelfWidth: 4

1. dp[0] = 0.
2. dp[1]: Only book 1. Height = 2. dp[1] = 2.
3. dp[2]:
   • Book 2 on its own shelf: dp[1] + 3 = 5.
   • Books 1 and 2 together (thick 1+2=3 < 4): dp[0] + max(2, 3) = 3.
   • dp[2] = 3.
4. dp[3]:
   • Book 3 on its own: dp[2] + 3 = 6.
   • Books 2 and 3 together (thick 2+2=4): dp[1] + max(3, 3) = 2 + 3 = 5.
   • Books 1, 2, and 3 together (thick 1+2+2=5 > 4): Invalid.
   • dp[3] = 5.

Common mistakes candidates make

• Greedy approach: Thinking that filling each shelf as much as possible will minimize height. (A short, thick book might be better on its own shelf if it's very tall).
• Ignoring the order: Trying to sort the books by height or thickness. The problem explicitly states books must be placed in the given order.
• O(N^2) Complexity: Not realizing that for each book $i$, you only need to look back as far as the shelf width allows, not the entire array.

Interview preparation tip

This is a "grouping" DP problem. Whenever you need to split a linear sequence into groups to optimize a cost, the dp[i] = min(dp[j] + cost(j, i)) pattern is usually the way to go.