Processing in the right order, then absorbing

Sort so that the collapse becomes local, then let a stack do the collapsing.

Here is the pattern on collisions. Values move right when positive and left when negative. Two that meet destroy the smaller in magnitude, or both if equal.

1def survivors(moving):2    stack = []3    for item in moving:4        alive = True5        while alive and stack and stack[-1] > 0 and item < 0:6            if stack[-1] < -item:7                stack.pop()              # the older one loses, keep testing8            elif stack[-1] == -item:9                stack.pop()              # both are destroyed10                alive = False11            else:12                alive = False            # the incoming one loses13        if alive:14            stack.append(item)15    return stack16 17print(survivors([5, 10, -5]))18print(survivors([8, -8]))19print(survivors([10, 2, -5]))

Quick check· 5 min

Which way should the scan run?

Cars travel along a road toward a shared finish line at different speeds and cannot pass each other. You want to count how many distinct groups arrive. In which order should the cars be processed?

Sorted by position, starting with the car closest to the finish, comparing arrival timesSorted by position, starting with the car furthest from the finish, comparing arrival timesSorted by speed, fastest firstSorted by arrival time, earliest first

Problem· 28 min

Car Fleet

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def survivors(moving):2 stack = []3 for item in moving:4 alive = True5 while alive and stack and stack[-1] > 0 and item < 0:6 if stack[-1] < -item:7 stack.pop() # the older one loses, keep testing8 elif stack[-1] == -item:9 stack.pop() # both are destroyed10 alive = False11 else:12 alive = False # the incoming one loses13 if alive:14 stack.append(item)15 return stack16 17print(survivors([5, 10, -5]))18print(survivors([8, -8]))19print(survivors([10, 2, -5]))