Count Collisions on a Road

Count Collisions on a Road

What is this problem about?

The Count Collisions on a Road interview question simulates cars moving on a single-lane road. Each car is moving either Left (L), Right (R), or is Stationary (S). When two moving cars collide, or a moving car hits a stationary one, they become stationary. You need to count the total number of collisions. A collision between two moving cars (RL) counts as 2, and a moving car hitting a stationary car (RS or SL) counts as 1.

Why is this asked in interviews?

Amazon and Bloomberg ask the Count Collisions on a Road coding problem to test your ability to simplify a complex simulation. While it looks like you need to track every car's movement over time, the problem can be reduced to a single-pass string processing task. It evaluates your "systems thinking" and ability to identify which cars will eventually collide.

Algorithmic pattern used

This is a Simulation / String Manipulation problem.

1. Identify that cars on the far left moving Left (LL...) and cars on the far right moving Right (...RR) will never collide.
2. Trim these non-colliding cars from the string.
3. Any remaining moving car (L or R) in the middle will eventually collide with something (either a stationary car or another car moving towards it).
4. Each L or R in the trimmed string contributes exactly 1 collision point.

Example explanation

road = "RLRSLL"

1. Trim non-colliding: None to trim (it starts with R and ends with L).
2. Count L and R in the remaining string:
   • R, L, R, L, L (5 moving cars).
   • The S in the middle doesn't count as a collision point but causes others to collide.
3. Each moving car in this middle section will eventually hit something.
4. Total collisions = 5. Wait, RL at the start is 2 points, but our logic handles it because R and L both count as 1.

Common mistakes candidates make

• Step-by-step Simulation: Trying to move the cars one unit at a time, which is too slow and complex.
• Ignoring Stationary Cars: Forgetting that a stationary car acts as a wall that triggers collisions.
• Wrong Count: Miscounting the RL collision (it's 2 points) or forgetting that once a car collides, it stays stationary.

Interview preparation tip

Always look for the "equilibrium" state in simulation problems. Ask yourself: "Which elements are guaranteed to change, and what will they look like when they stop?"