Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleFacebook

Car Pooling

Choose your preparation mode4 modes available
📋
Problem

Imagine you are managing a carpool service where multiple groups of passengers get on and off at different locations along a route. You need to ensure the car's capacity is never exceeded at any point.

You are driving a vehicle that can hold a fixed number of passengers (capacity). Given a list of trips, where each trip is represented as [num_passengers, start_location, end_location], determine if it is possible to pick up and drop off all passengers for all the given trips without exceeding the vehicle's capacity at any point. The vehicle only moves in one direction along a route from location 0 to location 1000.

1 ≤ number of trips ≤ 10^50 ≤ start_location < end_location ≤ 10001 ≤ num_passengers ≤ 10001 ≤ capacity ≤ 10^5
Edge cases: Single trip with passengers equal to capacity → should return trueTrips with no overlapping intervals → should return trueTrips where passengers get off exactly when others get on → should return true
</>
IDE
def carPooling(trips: list[list[int]], capacity: int) -> bool:public boolean carPooling(int[][] trips, int capacity)bool carPooling(vector<vector<int>>& trips, int capacity)function carPooling(trips, capacity)
def carPooling(trips, capacity):
    # Write your solution here
    pass
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Write your solution here
        return false;
    }
}
#include <vector>
using namespace std;

bool carPooling(vector<vector<int>>& trips, int capacity) {
    // Write your solution here
    return false;
}
function carPooling(trips, capacity) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: trueIgnoring overlapping intervals and summing passengers incorrectly, causing capacity overflow to be missed.✅ Implement event sorting and sweep line to accumulate passenger counts at each location and compare with capacity.
Wrong: falseOff-by-one error in interval handling, counting passengers at end location incorrectly.✅ Process drop-offs before pickups at the same location to avoid overcounting passengers.
Wrong: trueTreating trips as unbounded or reusing passengers multiple times (0/1 vs unbounded confusion).✅ Count passengers only once per trip interval; do not reuse or multiply counts.
Wrong: falseIncorrect handling of empty trips input, returning false or error instead of true.✅ Return true immediately if trips list is empty.
Wrong: TLEBrute force simulation of all locations for large inputs causing time limit exceeded.✅ Use event sorting and sweep line approach with O(n log n) complexity.
✓
Test Cases
t1_01basic
Input{"trips":[[2,1,5],[3,3,7]],"capacity":4}
Expectedfalse

Between locations 3 and 5, total passengers would be 2 + 3 = 5, which exceeds capacity 4.

t1_02basic
Input{"trips":[[2,1,5],[3,3,7]],"capacity":5}
Expectedtrue

Capacity 5 is sufficient for overlapping passengers 2 + 3 = 5 between locations 3 and 5.

t2_01edge
Input{"trips":[],"capacity":10}
Expectedtrue

No trips means no passengers, so capacity is never exceeded.

t2_02edge
Input{"trips":[[5,0,10]],"capacity":5}
Expectedtrue

Single trip with passengers equal to capacity should return true.

t2_03edge
Input{"trips":[[2,1,3],[3,3,5]],"capacity":3}
Expectedtrue

Passengers get off exactly when others get on; capacity never exceeded.

t3_01corner
Input{"trips":[[2,1,5],[3,2,6],[1,4,7]],"capacity":5}
Expectedfalse

Greedy approach picking earliest trips first fails; total passengers exceed capacity between locations 4 and 5.

t3_02corner
Input{"trips":[[1,0,2],[1,1,3],[1,2,4]],"capacity":1}
Expectedfalse

Confusing 0/1 vs unbounded: passengers cannot be reused multiple times; capacity exceeded between locations 1 and 2.

t3_03corner
Input{"trips":[[3,0,5],[2,5,10]],"capacity":3}
Expectedtrue

Off-by-one error test: passengers get off exactly when others get on; capacity never exceeded.

t4_01performance
Input{"trips":[[1000,0,500],[1000,500,1000]],"capacity":1000}
⏱ Performance - must finish in 2000ms

n=2 trips with max passengers and max location range; O(n log n) sweep line approach must complete within 2s.

Practice

(1/5)
1. Consider the following Python function implementing the line sweep algorithm to count intervals containing each point. Given intervals = [[1,4],[2,5],[7,9]] and points = [2,5,8], what is the final output of the function call count_intervals_line_sweep(intervals, points)?
easy
A. [2, 1, 1]
B. [2, 1, 0]
C. [1, 2, 1]
D. [2, 2, 1]

Solution

  1. Step 1: Sort events and process starts

    Events: (1,+1), (2,+1), (2,0), (5,0), (5+1,-1), (4+1,-1), (7,+1), (8,0), (9+1,-1). Sorted order processes starts before points, points before ends.
  2. Step 2: Track active intervals and assign counts at points

    At point 2: active=2 (intervals [1,4],[2,5]), at point 5: active=1 (only [2,5] ends at 6), at point 8: active=0 (interval [7,9] ended at 10, but 8 < 10 so active=1 actually, re-check)
  3. Correction Step 2:

    At point 8: interval [7,9] is active, so active=1. So final counts: [2,1,1]
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Counting active intervals at each point matches expected output [OK]
Hint: Remember to add 1 to interval ends for event ordering [OK]
Common Mistakes:
  • Forgetting end+1 shifts interval end
  • Misordering events causing wrong active count
  • Off-by-one in active count at points
2. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?
medium
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by end coordinate takes O(n log n) time.
  2. Step 2: Identify iteration cost

    Single pass through sorted intervals is O(n).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Dominant cost is sorting, so total is O(n log n) [OK]
Hint: Sorting dominates; iteration is linear [OK]
Common Mistakes:
  • Assuming linear time because of single pass
  • Confusing with brute force O(n^2)
  • Ignoring sorting cost
3. What is the time complexity of the optimal greedy algorithm that finds the maximum number of non-overlapping intervals by sorting intervals and iterating through them once?
medium
A. O(n log n) due to sorting plus O(n) iteration, total O(n log n)
B. O(n^2) due to nested comparisons between intervals
C. O(n) since it only iterates once through the intervals
D. O(n log n) because of sorting intervals by start or end time

Solution

  1. Step 1: Identify sorting cost

    Sorting intervals by start or end time takes O(n log n) time.
  2. Step 2: Identify iteration cost

    Iterating through the sorted intervals to select non-overlapping ones takes O(n) time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, total complexity is O(n log n) [OK]
Hint: Sorting dominates time complexity in interval scheduling [OK]
Common Mistakes:
  • Assuming iteration alone is O(n) and ignoring sorting
  • Mistaking nested loops causing O(n^2)
  • Confusing sorting and iteration costs
4. Suppose the intervals list can contain overlapping intervals initially (not guaranteed sorted or disjoint), and you want to insert a new interval and return the merged list. Which modification to the optimal approach is necessary to handle this variant correctly?
hard
A. Insert the new interval in the correct position without sorting, then merge only intervals overlapping with the new interval.
B. Append the new interval, then sort and merge all intervals including the original overlapping ones.
C. Skip sorting and merge intervals only if they overlap with the new interval to improve efficiency.
D. Use a balanced tree data structure to insert and merge intervals dynamically without sorting.

Solution

  1. Step 1: Understand initial intervals may overlap

    Since intervals are not guaranteed sorted or disjoint, merging must consider all intervals, not just those overlapping newInterval.
  2. Step 2: Modify approach to handle all overlaps

    Appending newInterval and sorting all intervals ensures correct order, then merging all intervals handles existing overlaps and new overlaps caused by insertion.
  3. Step 3: Why other options fail

    Options B and C assume partial merging which misses existing overlaps; D is overcomplicated and not required.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Sorting and merging all intervals handles arbitrary overlaps [OK]
Hint: Sort and merge all intervals when initial list may overlap [OK]
Common Mistakes:
  • Assuming initial intervals are sorted and disjoint
  • Trying partial merges only around new interval
  • Skipping sorting leads to incorrect merges
5. Suppose meetings can be scheduled with negative start or end times (e.g., representing times before a reference point). Which modification to the min-heap approach is necessary to correctly compute the minimum number of meeting rooms?
hard
A. Adjust the comparison in the heap to handle negative end times by using a max-heap instead of min-heap.
B. Sort intervals by absolute value of start times to handle negative values correctly.
C. Sort intervals normally by start time and use the min-heap approach as usual; negative times do not affect logic.
D. No modification needed; the existing min-heap approach works regardless of negative times.

Solution

  1. Step 1: Understand sorting by start time works with negative values.

    Sorting by start time orders intervals correctly even if times are negative.
  2. Step 2: Confirm min-heap logic remains valid.

    Heap tracks earliest end time; negative values do not affect min-heap property or comparison logic.
  3. Step 3: No need for absolute value sorting or max-heap.

    Using absolute values or max-heap breaks the logic of interval ordering and room reuse.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Negative times do not change sorting or heap logic [OK]
Hint: Sorting by start time works even with negative times [OK]
Common Mistakes:
  • Sorting by absolute values breaks interval order
  • Switching to max-heap unnecessarily
  • Assuming negative times require special handling
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard