Grumpy Bookstore Owner

Grumpy Bookstore Owner

What is this problem about?

The Grumpy Bookstore Owner interview question is an optimization problem. You are given an array of customers entering a store each minute, and a grumpy array where 1 means the owner is grumpy and 0 means they are not. When grumpy, the customers for that minute are not satisfied. The owner knows a secret technique to keep themselves from being grumpy for minutes consecutive minutes, but it can only be used once. You need to find the maximum number of customers that can be satisfied.

Why is this asked in interviews?

Companies like Amazon, Google, and Microsoft ask this Sliding Window coding problem to test a candidate's ability to separate base state from dynamic state. It evaluates whether you can compute a baseline sum (satisfied customers without the technique) and then use a sliding window to find the maximum "extra" satisfied customers the technique can provide.

Algorithmic pattern used

This problem uses the Fixed-Size Sliding Window pattern.

1. Baseline: Calculate the number of satisfied customers without using the technique (sum of customers[i] where grumpy[i] == 0).
2. Window Setup: Calculate the number of additional customers that would be satisfied if the technique was used for the first minutes window (sum of customers[i] where grumpy[i] == 1 in the first window). This is the current_extra.
3. Slide: Slide the window of size minutes across the array. For each step, add the new minute's unhappy customers to current_extra (if grumpy) and subtract the exiting minute's unhappy customers (if grumpy).
4. Maximize: Keep track of the max_extra seen.
5. Result: Total satisfied = Baseline + max_extra.

Example explanation

customers = [1, 0, 1, 2, 1, 1, 7, 5], grumpy = [0, 1, 0, 1, 0, 1, 0, 1], minutes = 3

1. Baseline (grumpy=0): $1 + 1 + 1 + 7 = 10$.
2. First window (indices 0,1,2): Unhappy customers = customers[1] (since grumpy[1]=1) = 0.
3. Slide to window (1,2,3): Add customers[3] (grumpy). Extra = $0 + 2 = 2$.
4. Slide to window (5,6,7): Extra = customers[5] + customers[7] = $1 + 5 = 6$. Max extra is 6. Total = Baseline (10) + Max extra (6) = 16.

Common mistakes candidates make

• Recalculating everything: Recalculating the entire sum of the window from scratch at each step, making the algorithm $O(N \cdot M)$ instead of $O(N)$.
• Mixing Base and Extra: Trying to slide a window that calculates the total satisfied customers directly. It's much easier to reason about the "bonus" customers independently from the "guaranteed" customers.
• Window Bounds: Off-by-one errors when subtracting the element that is falling out of the left side of the window.

Interview preparation tip

The "Baseline + Max Bonus" separation is a classic optimization trick. If a problem has a guaranteed minimum score and a limited "boost," calculate the guaranteed score in one pass, then use a sliding window to find the optimal place to apply the boost.