Robot Collisions

Robot Collisions

What is this problem about?

The Robot Collisions interview question gives you a list of robots on a number line, each with a position, health, and direction (L or R). Robots moving toward each other collide: the one with lower health is destroyed, and the survivor loses 1 health. If both have equal health, both are destroyed. Robots moving in the same direction never collide. Return the healths of surviving robots in their original order.

Why is this asked in interviews?

This HARD problem is asked at Samsung, Flipkart, Amazon, and Google because it is a real-world collision simulation requiring a stack-based approach. It combines sorting, stack processing, and result reconstruction while maintaining original ordering. It models physical simulations, game development (entity collision), and traffic flow analysis.

Algorithmic pattern used

The pattern is sort + stack simulation + result reconstruction. Sort robots by position to process collisions left to right. Use a stack to hold right-moving robots (they are candidates to collide with future left-moving robots). For each left-moving robot: while the stack is non-empty (right-moving robot at the top), simulate the collision. If the right-moving robot wins (higher health), it loses 1 health and remains on the stack. If the left-moving robot wins, pop the stack and continue. If equal, pop and the left-moving robot is destroyed. After processing all robots, surviving stack robots and unprocessed left-movers remain. Finally, reconstruct the answer in original order using saved indices.

Example explanation

Robots: positions=[3,5,2,6], health=[10,10,15,12], directions=['R','R','L','L']

Sort by position: (2,'L',15), (3,'R',10), (5,'R',10), (6,'L',12).

• (2,'L',15): stack empty → no collision, keep.
• (3,'R',10): push to stack. Stack: [(3,'R',10)].
• (5,'R',10): push. Stack: [(3,'R',10),(5,'R',10)].
• (6,'L',12): collide with stack top (5,'R',10): 12 > 10 → pop 5's robot, 6's health = 11. Next top (3,'R',10): 11 > 10 → pop, 6's health = 10. Stack empty → (6,'L',10) survives.

Survivors: (2,'L',15) and (6,'L',10). Original order result: [15, 10].

Common mistakes candidates make

• Not sorting by position before processing — collisions must be handled in spatial order.
• Forgetting to decrease the surviving robot's health by 1 after each collision.
• Not maintaining the original order for the output — track original indices separately.
• Treating same-direction robots as capable of colliding — they never collide.

Interview preparation tip

For the Robot Collisions coding problem, the array, sorting, and stack interview pattern is the framework. Sort by position, use a stack for rightward robots, process collisions when a leftward robot is encountered. Google and Samsung interviewers focus on the health-decrement detail and original-order reconstruction — be explicit about tracking indices. Practice on small examples with chain collisions before coding.