Implement bus route simulation features
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
### Bus Route Simulation – Boarding, Capacity, and Priority Passes
You are given a partially implemented codebase for simulating bus routes in a city. Buses travel along fixed routes with scheduled arrival times at each stop. Passengers appear at stops and want to travel to other stops.
Each **bus** has:
- A unique `bus_id`.
- A fixed **capacity** `C` (maximum number of passengers allowed on board at any time).
- A **schedule**: an ordered list of `(time, stop_id)` pairs indicating when the bus arrives at each stop.
Each **passenger** has:
- A unique `passenger_id`.
- `appear_time`: when the passenger appears at a stop.
- `from_stop`: the stop where they start.
- `to_stop`: the stop where they want to get off.
- `has_priority_pass`: a boolean indicating whether the passenger has a priority pass.
The simulation runs in **discrete time**. At each scheduled bus arrival `(time, stop_id)` for a bus:
1. The bus **drops off** all passengers currently on the bus whose `to_stop` equals `stop_id`.
2. The bus **picks up** waiting passengers at `stop_id` whose `appear_time <= time` and who have not yet boarded any bus.
3. The bus must **never exceed capacity** `C`.
4. You must **track and update** the number of passengers on board after each drop-off and pick-up.
The codebase defines basic data structures like `BusSchedule` and `PassengerEvent`, but several key functions are left for you to implement.
You may assume:
- Number of passenger events `E` is up to 100,000.
- Number of buses `B` is up to 1,000.
- Each bus schedule has at most 1,000 stops.
- All times are non-negative integers and you can assume that bus schedules and passenger events are available in memory.
#### Task 1 – Reduce Simulation Population
The full list of passenger events may be very large, making the simulation slow. Implement a function to **downsample** the passenger events to reduce the number of simulated passengers while approximately preserving the demand distribution across origin–destination pairs.
API (conceptual):
```text
List<PassengerEvent> downsamplePassengers(List<PassengerEvent> events, double factor)
```
where:
- `0 < factor <= 1` is a scale factor (e.g., `0.1` means simulate ~10% of the passengers).
- The result should:
- Contain roughly `factor * events.size()` passengers.
- Preserve the distribution of passengers across `(from_stop, to_stop)` pairs as much as reasonably possible.
Specify clearly how you choose which passengers to keep so that the distribution is roughly preserved.
#### Task 2 – Boarding and Dropping Logic with Capacity Tracking
Implement the main simulation logic that handles bus boarding and dropping, ensuring capacities are never exceeded and on-board counts are correctly tracked.
API (conceptual):
```text
List<LogEntry> simulate(
List<BusSchedule> busSchedules,
List<PassengerEvent> passengers,
int capacity
)
```
where each `LogEntry` has:
- `time`
- `bus_id`
- `stop_id`
- `passenger_id`
- `action` in {"board", "drop"}
Simulation rules:
- For each `(time, stop_id)` in each `BusSchedule`, process events in **time order**.
- At each bus arrival:
1. Drop off all passengers on that bus whose `to_stop == stop_id` (emit `"drop"` log entries).
2. Among waiting passengers at `stop_id` with `appear_time <= time` and not yet boarded any bus, pick up passengers **without ever exceeding capacity**.
- Initially, all buses have zero passengers.
- You must maintain and update the **current passenger count** for each bus after each `board`/`drop`.
Your implementation should be efficient enough to handle the stated constraints.
#### Task 3 – Validate Logs and Find Bugs
You are given a log generated by some (possibly buggy) version of the simulation. You need to verify whether the log respects the bus capacity constraints and basic consistency rules.
API (conceptual):
```text
boolean validateLog(List<LogEntry> log, int capacity)
```
The validator should check at least the following:
- Bus occupancy for any bus **never becomes negative**.
- Bus occupancy for any bus **never exceeds** `capacity`.
- A passenger **cannot drop off before boarding**.
- A passenger **cannot board more than once** (i.e., cannot be on multiple buses or board the same bus twice).
You may also return the first error found (e.g., by returning an error description instead of just `boolean`), but at minimum you must be able to detect whether the log is valid or not.
Describe the state you need to track while scanning the log and how you update it.
#### Task 4 – Support Priority Passengers
Extend your boarding logic in **Task 2** to support priority passes:
- Passengers with `has_priority_pass == true` should be boarded **before** non-priority passengers when a bus arrives at a stop.
- Within the same priority level (priority vs non-priority), passengers should board in **arrival order** (`appear_time` ascending, breaking ties consistently, e.g., by `passenger_id`).
- Capacity constraints must still be strictly enforced.
Update `simulate(...)` so that log entries reflect this behavior, and the on-board passenger counts remain correct.
For all tasks, clearly define and use appropriate data structures, and design your solution to run efficiently for the given input sizes.
Quick Answer: This question evaluates a candidate's skills in stateful event-driven simulation, data-structure and algorithm design for capacity-constrained boarding and dropping logic, and statistical downsampling to preserve origin–destination demand distributions.