Car Fleet

Car Fleet

What is this problem about?

The Car Fleet interview question asks you to find the number of "car fleets" that will arrive at a target destination. You are given the target distance, an array of position values, and an array of speed values for n cars. A car fleet is a group of one or more cars traveling at the same speed because a faster car caught up to a slower car ahead of it. Faster cars cannot pass slower ones; they simply slow down and join the fleet. This Car Fleet coding problem is about calculating time-to-destination and identifying collisions.

Why is this asked in interviews?

Companies like Google, Microsoft, and Meta use this to test a candidate's ability to process events based on their physical constraints. It evaluates whether you can recognize that the problem is best solved by processing cars from the one closest to the target backward. It tests your proficiency with sorting and stack-based logic.

Algorithmic pattern used

This problem utilizes the Array, Monotonic Stack, Sorting, Stack interview pattern.

1. Pair each car's position with its speed and sort them by position in descending order (closest to target first).
2. Calculate the time each car would take to reach the target: (target - position) / speed.
3. Iterate through the sorted cars. If a car's time is greater than the time of the fleet ahead of it, it starts a new fleet. If its time is <=, it joins the fleet ahead.

Example explanation

target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

1. Car A (Pos 10, Speed 2): Time = (12-10)/2 = 1.
2. Car B (Pos 8, Speed 4): Time = (12-8)/4 = 1. (Joins A).
3. Car C (Pos 5, Speed 1): Time = (12-5)/1 = 7. (New fleet).
4. Car D (Pos 3, Speed 3): Time = (12-3)/3 = 3. (Joins C).
5. Car E (Pos 0, Speed 1): Time = (12-0)/1 = 12. (New fleet). Total Fleets: 3.

Common mistakes candidates make

• Sorting by Speed: Trying to solve the problem by sorting cars based on how fast they are going, which doesn't account for their starting positions.
• Ignoring the "No Passing" Rule: Assuming faster cars can overtake slower ones.
• Floating Point Precision: Not using double/float for time calculations, which can lead to rounding errors.

Interview preparation tip

When objects are moving in a line and cannot pass each other, always try to solve the problem by looking at the "leader" (the one furthest ahead). The behavior of everyone behind is restricted by the leaders.