The Pizza With 3n Slices problem gives you a circular pizza of 3n slices. Three people (you, Alice, Bob) take turns picking slices: Alice and Bob always pick slices adjacent to you, so effectively you can never pick two adjacent slices and cannot pick the first and last slice together (circular constraint). Pick n non-adjacent slices to maximize your total. This hard coding problem is a circular "house robber" variant. The array, heap, greedy, and dynamic programming interview pattern is the core.
Amazon and Google ask this because it combines the circular house robber constraint (no two adjacent, can't take first and last together) with maximizing n choices — a harder variant than just "max sum of non-adjacent." The greedy priority queue approach or two DP passes solve it.
Two DP passes (circular house robber generalization). Break the circular constraint into two linear DPs: (1) exclude the first slice (indices 1..3n-1), (2) exclude the last slice (indices 0..3n-2). For each, find the maximum sum of n non-adjacent elements. The answer is the max of both DPs.
Greedy heap approach: Use a max-heap. Pick the max slice, remove it and its neighbors (they become unavailable), replace neighbors in the heap with their sum (virtual merge). Repeat n times.
slices=[1,2,3,4,5,6], n=2 (pick 2 from 6=3*2 slices, max non-adjacent from circular). Pass 1 (indices 1-5=[2,3,4,5,6]): max 2 non-adjacent = 4+6=10 or 3+5=8. Max=10? But we need non-adjacent: from [2,3,4,5,6]: 6+4=10 ✓ (not adjacent in linear). Pass 2 (indices 0-4=[1,2,3,4,5]): max 2 non-adjacent: 1+3=4? 1+4? 5+3=8? 5+2? 4+2=6 or 5+1=6... max = 5+3=8? No: 5 is at index 4, 3 at index 2: not adjacent ✓. Max=8. Answer = max(10,8) = 10.
Pizza With 3n Slices generalizes "house robber on a circle" to "pick exactly k non-adjacent elements from a circle." The two-pass linear DP approach (circular → two linear cases) is the key transformation. Practice: "house robber II" (pick max sum non-adjacent from circle), then "pick exactly k non-adjacent from circle." These require careful DP state design with the count dimension.
