Reducing Dishes

Reducing Dishes

What is this problem about?

The Reducing Dishes problem gives you dish satisfaction scores. You cook dishes in some order; the i-th cooked dish contributes i × satisfaction[i]. Find the maximum total "like-time coefficient" by choosing a subset of dishes in the optimal order (can discard some). This hard coding problem uses greedy sorting with suffix sums. The array, sorting, greedy, and dynamic programming interview pattern is demonstrated.

Why is this asked in interviews?

Sony, Microsoft, Amazon, and Google ask this because the key insight — sort in ascending order and include dishes from the right as long as their addition increases the total — is non-obvious. The suffix sum technique confirms when to stop including dishes.

Algorithmic pattern used

Sort descending + greedy from right. Sort in ascending order. The optimal order is to cook dishes from most satisfying to least satisfying. Starting from the most satisfying dish, include dishes from right to left as long as the running sum (suffix sum) is positive. Each additional dish contributes its value to ALL already-chosen dishes' coefficients.

The total gain of adding one more dish = suffix_sum (each current dish shifts one position later) + dish_value. Add while suffix_sum + dish_value > 0.

Example explanation

satisfaction=[-1,-8,0,5,-9]. Sort: [-9,-8,-1,0,5]. Suffix from right: start with 5. suffix_sum=5. Add 0: 5+0=5>0 ✓. Add -1: 5+(-1)=4>0 ✓. Add -8: 4+(-8)=-4≤0 ✗. Stop. Total = 3×5 + 2×0 + 1×(-1) = 15+0-1 = 14 (or compute via DP).

Common mistakes candidates make

• Not sorting before the greedy decision.
• Not recognizing that each added dish shifts all current dishes' time coefficients.
• Trying all possible subsets (exponential).
• DP approach: dp[i] = max(dp[i-1], dp[i-1]+suffix_sum).

Interview preparation tip

Reducing Dishes is a greedy problem disguised as a DP problem. The key observation: always cook better dishes first; include a dish from the left only if it adds more than it costs to shift all others right by one. Sort and compute suffix sums — when suffix sum goes negative, stop. Practice greedy problems where "what's the gain of including one more item" is the deciding question.