Car Fleet
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Cars at different positions drive toward one target on a single lane and cannot overtake. A car that catches a slower one joins its fleet. Count the fleets that arrive.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How long would each car take to reach the target if it drove alone?
- Hint 2Process the cars from the one closest to the target. When does a car start a new fleet?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A narrow one-lane road to a village. Each car would reach the village in some number of hours if alone. Start with the car closest to the village. A car behind it that would arrive sooner cannot pass: it gets stuck behind and arrives together with the car in front (one fleet). A car behind that would arrive later is truly separate and starts a new fleet.
- The obvious way
Simulate the road minute by minute, merging cars when they meet: slow and fiddly.
- The key insight
Compute each car's solo arrival time = (target - position) / speed. Go through cars from nearest to the target to farthest. Keep the arrival time of the current front fleet. If a car's time is longer than that, it never catches up: new fleet, and its time becomes the front fleet's time. If it is shorter or equal, it merges into the fleet ahead.
- The algorithm
- Pair each position with its speed and sort by position, closest to the target first.
- Time for a car = (target - position) / speed.
- Keep the time of the front fleet. A car with a LONGER time starts a new fleet (count + 1, update the front time).
- A car with a shorter or equal time joins the fleet ahead.
Watch it run
Exampletarget = 12, positions = [10, 8, 0, 5, 3], speeds = [2, 4, 1, 1, 3]
Closest car (position 10, speed 2) needs 1 hour. It starts the first fleet.
fleets 1, front time 1
Where people slip
- Use real division for times; integer division can make two different arrival times look equal.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def car_fleet(target, position, speed):
cars = sorted(zip(position, speed), reverse=True) # closest to the target first
fleets = 0
front_time = 0 # arrival time of the fleet ahead
for place, velocity in cars:
time = (target - place) / velocity
if time > front_time: # cannot catch up: a new fleet
fleets += 1
front_time = time
return fleetsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.