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.

Validate carpool capacity | Meta Coding Question

Validate carpool capacity

Company: Meta

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question LeetCode 1094. Car Pooling – Given trips[i] = [numPassengers, start, end] and an integer capacity, return true if the vehicle can fulfill all trips without exceeding capacity at any point; otherwise return false. https://leetcode.com/problems/car-pooling/description/

Quick Answer: This question evaluates understanding of interval-based resource accounting and algorithmic reasoning with cumulative constraints, assessing skills in processing time-bound events and managing capacity limits.

You are driving a vehicle that has `capacity` empty seats initially available for passengers. The vehicle only drives east (i.e., it cannot turn around and drive west). You are given the integer `capacity` and an array `trips` where `trips[i] = [numPassengers, start, end]` indicates that the i-th trip has `numPassengers` passengers and the locations to pick them up and drop them off are `start` and `end` respectively. The locations are given as the number of kilometers due east from the vehicle's initial location. Return `true` if it is possible to pick up and drop off all passengers for all the given trips without exceeding `capacity` at any point along the route, or `false` otherwise. Note: a passenger occupies a seat over the half-open interval `[start, end)` — they are dropped off exactly at `end`, so a new pickup at the same location as a drop-off does not conflict. Example: - Input: trips = [[2,1,5],[3,3,7]], capacity = 4 -> Output: false (between km 3 and 5, 5 passengers are aboard, exceeding capacity 4) - Input: trips = [[2,1,5],[3,3,7]], capacity = 5 -> Output: true

Constraints

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengers <= 100
0 <= start < end <= 1000
1 <= capacity <= 100000

Examples

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

Expected Output: False

Explanation: Between km 3 and 5, both trips overlap: 2 + 3 = 5 passengers aboard, exceeding capacity 4 -> false.

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

Expected Output: True

Explanation: Peak occupancy is 5 (km 3-5), which equals capacity 5, so it never exceeds -> true.

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

Expected Output: True

Explanation: The first trip ends at km 5 exactly when the second begins, so they never overlap; max aboard is 3 = capacity -> true.

Input: ([], 0)

Expected Output: True

Explanation: No trips means no passengers are ever aboard, so capacity is never exceeded -> true.

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

Expected Output: True

Explanation: A single full-route trip of 5 passengers exactly fills capacity 5 -> true.

Input: ([[6, 0, 1000]], 5)

Expected Output: False

Explanation: A single trip of 6 passengers exceeds capacity 5 from the very start -> false.

Input: ([[3, 2, 7], [3, 7, 9], [8, 3, 9]], 11)

Expected Output: True

Explanation: Peak occupancy: km 3-7 has trips 1 and 3 = 3 + 8 = 11; the second trip starts at km 7 as the first drops off, keeping max at 11 = capacity -> true.

Hints

Think of each trip as +numPassengers at `start` and -numPassengers at `end`. The occupancy only changes at these event points.
Use a difference array indexed by location: add passengers at `start`, subtract them at `end`. A prefix sum over it gives the number of passengers aboard at every location.
Sweep the prefix sum from left to right; if it ever exceeds `capacity`, return false. Because drop-off happens exactly at `end`, subtracting at index `end` (not end+1) correctly frees the seat before any same-location pickup.

Quick Overview

This question evaluates understanding of interval-based resource accounting and algorithmic reasoning with cumulative constraints, assessing skills in processing time-bound events and managing capacity limits.