Eat Pizzas!

Eat Pizzas!

What is this problem about?

The Eat Pizzas! interview question involves n pizzas, each with a specific weight. You want to eat all pizzas over several days. Each day, you pick exactly 4 pizzas. On odd-numbered days (1, 3, 5...), you get to eat the heaviest pizza of the 4. On even-numbered days (2, 4, 6...), you get to eat the second-heaviest pizza of the 4. You need to determine the maximum total weight of pizzas you can eat.

Why is this asked in interviews?

Infosys and similar companies use this greedy interview pattern to test a candidate's ability to optimize a selection process under specific constraints. It requires sorting and a clear strategy for how to "pair" pizzas each day to maximize your gain. It evaluates whether you can derive the mathematical indices for the elements you should pick from a sorted array.

Algorithmic pattern used

This problem is solved using Sorting and a Greedy approach.

1. Sort all pizzas by weight in ascending order.
2. The total number of days is n / 4.
3. Let odd_days be the number of odd-numbered days and even_days be the number of even-numbered days.
4. On odd days, you want the absolute heaviest available pizzas.
5. On even days, you need to "waste" one heavy pizza to get the second-heaviest.
6. Strategy:
   • Pick the odd_days heaviest pizzas from the end of the array.
   • For even days, pick the next set of pizzas but skip one for every day to satisfy the "second-heaviest" rule.

Example explanation

Suppose n = 8 pizzas (2 days). Weights: [1, 2, 3, 4, 5, 6, 7, 8].

• Day 1 (Odd): You get the heaviest.
• Day 2 (Even): You get the second heaviest.

1. Sort: [1, 2, 3, 4, 5, 6, 7, 8].
2. Odd days (1): Pick weight 8.
3. Even days (1): To get the second heaviest, you must group a heavier one. Use 7 and pick 6.
4. The remaining pizzas [1, 2, 3, 4, 5] are just filler. Total Weight: 8 + 6 = 14.

Common mistakes candidates make

• Not Sorting: Trying to use a max-heap or searching for the best pizzas repeatedly, which is O(N^2).
• Incorrect Indexing: Forgetting that on even days, you "consume" two heavy pizzas to get the value of one (the second heaviest).
• Day Parity Confusion: Misapplying the rule for odd vs. even days.

Interview preparation tip

Whenever you need to maximize a sum of "best" elements under grouping rules, sorting is the first step. Think about which elements are "wasted" and which are "collected" to find the optimal indices.