How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Meta during technical interviews.

Check carpool trip feasibility | Meta Coding Question

Q: Check carpool trip feasibility

This question evaluates understanding of sweep-line algorithms, interval/event aggregation, and complexity analysis for capacity-constrained scheduling on a one-dimensional route, including handling simultaneous events and edge cases in event ordering.

Check carpool trip feasibility

Company: Meta

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given a list of trips where each trip i is (passengers_i, start_i, end_i) with start_i < end_i on a one-dimensional route. A single vehicle with capacity C moves in the increasing direction only; passengers board at start_i and alight at end_i. Implement can_complete_carpool(trips, C) that returns True iff all trips can be completed without exceeding capacity at any point. Use a sweep-line approach with +passengers at start_i and -passengers at end_i; target time/position complexity O(n log n). Discuss edge cases when multiple events share the same coordinate.

Quick Answer: This question evaluates understanding of sweep-line algorithms, interval/event aggregation, and complexity analysis for capacity-constrained scheduling on a one-dimensional route, including handling simultaneous events and edge cases in event ordering.

You are given a list of `trips`, where each trip is `(passengers, start, end)` with `start < end` on a one-dimensional route. A single vehicle with capacity `C` moves only in the increasing direction. For each trip, `passengers` board at position `start` and alight at position `end`. Implement `can_complete_carpool(trips, C)` that returns `True` if and only if every trip can be completed without the number of passengers on board exceeding `C` at any point along the route, and `False` otherwise. Use a sweep-line approach: emit a `+passengers` event at each `start` and a `-passengers` event at each `end`, sort the events by coordinate, and scan left to right tracking the running occupancy. Target complexity is O(n log n) time. Edge case to handle carefully: when a drop-off and a pickup share the same coordinate, the passenger alighting at that position frees their seat *before* the boarding passenger takes one. Process the negative (alight) event before the positive (board) event at any tied coordinate.

Constraints

0 <= len(trips) <= 10^5
1 <= passengers_i <= 10^4
0 <= start_i < end_i <= 10^9
0 <= C <= 10^9

Examples

Input: ([[2, 1, 5], [3, 3, 7]], 4)

Expected Output: False

Explanation: Trips overlap on [3,5]: occupancy reaches 2+3=5 > 4, so the carpool fails.

Input: ([[2, 1, 5], [3, 3, 7]], 5)

Expected Output: True

Explanation: Same overlap peaks at exactly 5 = C, which is allowed.

Input: ([[2, 1, 5], [3, 5, 7]], 3)

Expected Output: True

Explanation: Trips meet at coordinate 5: the first trip alights before the second boards, so max occupancy is 3 <= C.

Input: ([], 0)

Expected Output: True

Explanation: No trips means nothing to violate; trivially feasible.

Input: ([[5, 0, 10]], 4)

Expected Output: False

Explanation: A single group of 5 exceeds capacity 4.

Input: ([[5, 0, 10]], 5)

Expected Output: True

Explanation: A single group of 5 exactly fills capacity 5.

Input: ([[1, 1, 2], [1, 2, 3], [1, 3, 4]], 1)

Expected Output: True

Explanation: Back-to-back trips each reuse the single seat at the shared coordinate; occupancy never exceeds 1.

Input: ([[3, 2, 8], [4, 4, 6], [10, 8, 9]], 11)

Expected Output: True

Explanation: Peak occupancy is 3+4=7 on [4,6]; at coordinate 8 the first group (3) alights before the group of 10 boards, so occupancy reaches 10 <= 11.

Hints

Turn each trip into two events: a pickup (+passengers) at start and a drop-off (-passengers) at end. Sort all events by coordinate.
Sweep left to right accumulating a running occupancy. If it ever exceeds C, return False.
When a drop-off and a pickup land on the same coordinate, process the drop-off first (sort negative deltas before positive ones at equal coordinates) so a freed seat can be immediately reused.

Quick Overview

This question evaluates understanding of sweep-line algorithms, interval/event aggregation, and complexity analysis for capacity-constrained scheduling on a one-dimensional route, including handling simultaneous events and edge cases in event ordering.