Trimming the playout

The news bulletin at the top of the hour is three minutes long and the hour is three minutes short. One segment near the end of the playout has to go.

The problem

A radio station queues what it will broadcast as a playout chain: each segment carries an id and a pointer to the segment that follows it. The automation reads the chain forward, one segment at a time, and cannot step back — rewinding means asking the scheduler for the whole chain again, which nobody has time for during a live hour.

The producer counts from the end, not the start: "drop the second-from-last segment", where the last segment is 1. Nobody knows how many segments are queued, because items are still being appended behind you. Remove that one segment and hand back what will now air, in order, having walked the chain once.

Input. playout — a list of segment ids, in the order they are due to air. k — an integer counting from the end, where k = 1 is the last segment.

Output. The list of ids that remain, in order.

Example.

playout = [881, 902, 915, 940, 963], k = 2   ->  [881, 902, 915, 963]

Counting back from the end: 963 is 1, 940 is 2. Segment 940 comes out and the chain closes over it.

A second example, where k reaches the front of the chain:

playout = [881, 902, 915, 940, 963], k = 5   ->  [902, 915, 940, 963]
playout = [412], k = 1                       ->  []

When k equals the length the segment removed is the head, which has no predecessor to re-point; when the chain holds one segment the answer is an empty playout.

Constraints.

• 1 <= len(playout) <= 10^5
• 1 <= k <= len(playout)
• 1 <= segment id <= 10^6; ids may repeat, since a jingle can air twice
• One forward pass over the chain, O(1) extra memory.

Hints

Approach

Brute force

Walk the chain counting segments to get n, then walk again to segment n - k - 1 and unhook. That is 2n steps in two passes, and the second pass is exactly what the desk cannot afford.

The insight

Two markers held exactly k + 1 apart turn "k from the end" into "at the end": when the leading marker runs off the chain, the trailing one is standing on the predecessor of the segment to drop, and no length was ever computed.

The gap is set once, by advancing the lead alone, and never changes afterwards because both markers then move one segment per step. That pins the trail to the lead, and the lead's stopping point — the end of the chain — is recognisable without knowing where it is.

The gap is k + 1 rather than k because a deletion has to stand on the predecessor of the target. Starting both markers at a dummy segment in front of the head gives even the head a predecessor, so k = n needs no branch.

Algorithm

1. Put a dummy segment in front of the head; set lead and trail to it.
2. Advance lead alone k + 1 times.
3. While lead is not None, advance lead and trail one step each.
4. Unhook: trail.next = trail.next.next.
5. Return dummy.next.

Complexity

Time O(n) — the lead touches each segment once and the trail a suffix, at most 2n pointer reads in one forward pass. Space O(1) — a dummy and two markers, whatever the length of the playout.

Solution

"""Trimming the playout — two markers a fixed gap apart in one forward pass."""


class Segment:
    """One playout item; `nxt` is the segment due to air after it."""

    def __init__(self, sid, nxt=None):
        self.sid = sid
        self.nxt = nxt


def queue_up(ids):
    """Build the playout chain and return its head."""
    head = None
    for sid in reversed(ids):
        head = Segment(sid, head)
    return head


def read_chain(head):
    """Walk the chain and write out the ids in airing order."""
    ids = []
    while head:
        ids.append(head.sid)
        head = head.nxt
    return ids


def solve(playout, k):
    dummy = Segment(0, queue_up(playout))   # gives the head a predecessor

    lead = trail = dummy
    for _ in range(k + 1):                  # open the gap once, then hold it
        lead = lead.nxt
    while lead:
        # invariant: lead is exactly k + 1 segments ahead of trail, so when
        # lead falls off the end trail sits on the target's predecessor.
        lead = lead.nxt
        trail = trail.nxt
    trail.nxt = trail.nxt.nxt               # unhook the segment k from the end

    return read_chain(dummy.nxt)

TESTS = [
    (([881, 902, 915, 940, 963], 2), [881, 902, 915, 963]),
    (([881, 902, 915, 940, 963], 5), [902, 915, 940, 963]),
    (([881, 902, 915, 940, 963], 1), [881, 902, 915, 940]),
    (([412], 1), []),
    (([50, 50, 50], 2), [50, 50]),
    ((list(range(1, 101)), 100), list(range(2, 101))),
]

Pitfalls

• Opening the gap k times instead of k + 1. The trail ends up standing on the target itself, so trail.next = trail.next.next drops the segment after it: the first example returns [881, 902, 915, 940], keeping 940 on air and losing the closing segment 963.
• Returning head instead of dummy.next. When k equals the length, the head is the segment that was removed, so the caller gets the full five-segment playout back unchanged and the hour still overruns.
• No dummy at all. Then k = n needs its own branch, and the branch is the one nobody tests: a one-segment chain with k = 1 either returns [412] or raises on a None predecessor.

Variants

• One shelving run — the same dummy head, building a chain instead of cutting one.
• Sluice gate loop — two markers again, but one moves twice as fast instead of keeping a fixed gap.