Car Pooling

Car Pooling

What is this problem about?

The Car Pooling interview question asks if a car with a fixed capacity can complete a series of trips. Each trip is defined as [num_passengers, start_location, end_location]. Passengers must be picked up and dropped off exactly at the specified locations. You need to determine if at any point the number of passengers in the car exceeds its capacity. This Car Pooling coding problem is a resource allocation task.

Why is this asked in interviews?

Companies like Lyft, Goldman Sachs, and Amazon use this to test a candidate's ability to handle interval-based events. It evaluates whether you can efficiently track changes in state over a 1D timeline. The problem can be solved in O(N log N) using sorting or O(Max_Location) using a difference array.

Algorithmic pattern used

This follows the Array, Sorting, Simulation, Prefix Sum interview pattern, specifically the Difference Array (Sweep Line) technique.

1. Create an array (or map) where arr[i] represents the net change in passengers at location i.
2. For each trip, add passengers at start and subtract them at end.
3. Traverse the array from start to end, maintaining a running sum of passengers.
4. If the running sum ever exceeds capacity, return false.

Example explanation

capacity = 4, trips = [[2, 1, 5], [3, 3, 7]]

• At location 1: +2 passengers. (Total: 2).
• At location 3: +3 passengers. (Total: 5).
• Since 5 > 4, the car is over capacity at location 3.
• Result: False.

Common mistakes candidates make

• Not dropping off soon enough: Forgetting that passengers leave at the end_location. If a trip is [2, 1, 5], the car is free at location 5, not location 6.
• Sorting only by start time: If using a sorting approach, you must handle both pickups and drop-offs as separate events and sort them correctly.
• Inefficient loops: Using a nested loop to increment every mile of a trip (O(N * Distance)), which is slow if trips are long.

Interview preparation tip

Master the "Difference Array" pattern. It is the most efficient way to handle "Range Add" queries when you only need the final state or need to check a global constraint across all points.