# Skip a Beat > Two in a row is never allowed. Collect the most from what remains. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## Problem You're picking which slots to run on a single worker that needs a cooldown between jobs, so two back-to-back slots can never both run. Given `payoffs`, the value of each slot in order, return the most total value you can collect without ever choosing two adjacent slots. ## Worked solution and explanation ### What this problem really is This is the classic pick-a-non-adjacent-subset-for-max-sum problem wearing a scheduling costume. The tempting move is greedy: sum every other slot, or always grab the bigger of two neighbors. It passes on gentle inputs and then quietly returns the wrong number, because the best choice at slot i is not a fixed pattern. It is whichever is larger: the best total you already had before slot i, or the best from two slots back plus slot i's own value. Miss that and [2, 1, 1, 2] hands you 3 when the answer is 4, because the winning move is to skip two in a row and take both ends. > **Trick to solving** > > Never decide slot by slot with a fixed rule. Carry two running bests as you sweep: the best total that ends by taking the current slot, and the best that skips it. Each new slot is one max and one add away from both. --- ### Building it #### Step 1: Track two running bests Keep two numbers as you move left to right: `take`, the best total that uses the current slot, and `skip`, the best total that leaves it out. Both start at 0 for the empty prefix, which is also why an empty list returns 0 for free. #### Step 2: Update them slot by slot For each `value`, the new `take` is the old `skip` plus `value` (you could not have used the previous slot), and the new `skip` is the better of the old `take` and `skip`. Update both at once so neither read sees a half-updated value. The answer is the larger of the two at the end. --- ### The solution **Non-adjacent max sum in one pass with two running bests** ```python def max_payoff(payoffs: list) -> int: take, skip = 0, 0 for value in payoffs: take, skip = skip + value, max(take, skip) return max(take, skip) ``` > **Time and space** > > **Time:** O(n), a single sweep with constant work per slot. **Space:** O(1), just the two running totals. No table to allocate, no recursion stack. **Greedy parity scan** Sum the even-indexed slots, or grab each local max. Fast and intuitive, but it commits to a fixed stride. On [2, 1, 1, 2] it returns 3, never seeing that taking both 2s (indices 0 and 3, not adjacent) totals 4. **Two running bests** At each slot, compare skipping it against taking it plus the best from two slots back. This weighs both ends of [2, 1, 1, 2] and returns 4. Same single pass, correct every time. > **Interviewers watch for** > > The tell is whether you reach for a parity trick or set up the take/skip pair. Candidates who greedily alternate and 'check it on an example' usually pick an example where alternation happens to win. Naming why the choice at each slot depends on two earlier subproblems is the senior signal. > **Common pitfall** > > Assuming the optimum alternates: take slots 0, 2, 4, or every odd index. It passes plenty of inputs and then fails silently on ones like [2, 1, 1, 2], where the best selection skips two in a row to grab both ends. --- ## Common follow-up questions - How would your solution change if a slot's value could be negative? _(Tests whether the candidate realizes a negative slot is never worth taking, so comparing against skipping still holds.)_ - Can you recover which slots were chosen, not just the total? _(Tests reconstructing the chosen slots by backtracking the take/skip decisions rather than only returning the total.)_ - What if the slots were arranged in a circle, so the first and last are adjacent? _(Tests the circular variant: first and last become adjacent, so you run the linear solve twice, excluding either endpoint, and take the max.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/skip_a_beat) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.