What's Left Standing

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
BCG Securities

Problem

A one-dimensional physics sim hands you a row of moving particles as nonzero integers, where the sign is the direction (positive drifts right, negative drifts left) and the magnitude is the mass. Particles collide only when a right-mover is caught up to a left-mover ahead of it; the heavier one survives the impact and keeps going, while same-direction or diverging particles pass untouched. Return particles after every collision has played out, in its original order.

They only meet head-on, and only mass decides who keeps going.

Example 1

Input:

particles = [5,10,-5]

Output:

[5,10]

Example 2

Input:

particles = [10,2,-5]

Output:

[10]

Worked solution and explanation

What this problem really is

Strip the sci-fi costume and this is a cascading pairwise-reduction problem: as you sweep left to right, each left-moving particle has to fight not just its neighbor but every right-moving survivor still standing behind it, most recent first. That last-in-first-out challenge order is the entire problem. Anyone can compare two adjacent particles. The separator is realizing that destroying one survivor can re-expose an earlier one that now has to fight the same incoming particle, which is exactly what a growable stack of survivors gives you. Miss it and [10, 2, -5] keeps the 2 or drops the 10: a heavy left-mover that should plow through several right-movers stops at the first.

Break down the requirements

Step 1: Read the sign, not the number

The sign is the direction and the magnitude is the mass. A collision is possible only when a right-moving particle (positive) is immediately to the left of a left-moving particle (negative), so they close on each other. Two particles moving the same way, or a left-mover already ahead of a right-mover, drift apart and never meet.

Step 2: Keep a stack of survivors

Sweep the row left to right and keep a stack of the particles that have survived so far. A right-mover always gets pushed: nothing behind it can catch it. The interesting case is an incoming left-mover, because it is the only thing that can collide with what is already on the stack.

Step 3: Resolve the cascade with an inner loop

When a left-mover arrives, run an inner loop while it is still alive and the top of the stack is a right-mover. Compare masses: if the top is lighter, pop it and let the left-mover keep fighting the next survivor; if they are equal, pop the top and the left-mover also dies; if the top is heavier, the left-mover dies. If it survives the whole gauntlet (the stack empties of right-movers, or the top is another left-mover), push it.

The solution

Single-pass stack reduction
def resolve_collisions(particles):
    survivors = []
    for particle in particles:
        alive = True
        while alive and particle < 0 and survivors and survivors[-1] > 0:
            top = survivors[-1]
            if top < -particle:
                survivors.pop()          # lighter right-mover explodes, keep fighting
            elif top == -particle:
                survivors.pop()          # equal mass, both explode
                alive = False
            else:
                alive = False            # heavier right-mover survives, incoming dies
        if alive:
            survivors.append(particle)
    return survivors
Adjacent-only pass
Walk the list once and compare each particle to the one before it. Works on [5, 10, -5] by luck, but on [10, 2, -5] it destroys the 2 and stops, keeping [10, 2]. A heavy left-mover never reaches the survivors hiding behind the first thing it kills.
Stack of survivors
Push survivors; when a left-mover arrives, pop lighter right-movers off the top one by one until it dies, ties, or the top is no longer a right-mover. Re-exposing an earlier survivor is automatic, because it is simply the new top of the stack.

Common follow-up questions