Skip a Beat

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Citadel

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.

Two in a row is never allowed. Collect the most from what remains.

Example 1

Input:

payoffs = [2,7,9,3,1]

Output:

12

Example 2

Input:

payoffs = [2,1,1,2]

Output:

4

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.

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
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)
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.

Common follow-up questions