Compute Earliest Bus Arrival
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given several bus routes connecting multiple stops. Each route can be represented as directed segments between consecutive stops. For every segment from stop `A` to stop `B`, you know:
- `travel_time`: how many minutes the bus takes to go from `A` to `B`
- `wait_interval`: how often a bus departs from `A` toward `B`
Assume buses on a segment depart every `wait_interval` minutes, starting at time `0`. If a traveler reaches stop `A` at time `t`, they must wait until the next valid departure time on that segment before traveling to `B`.
Given:
- a set of bus segments
- a start stop `source`
- an end stop `target`
- a starting time `start_time`
return the earliest possible arrival time at `target`. If `target` cannot be reached, return an indication such as `-1`.
You should also discuss the time complexity of your approach and the important edge cases you would test.
Quick Answer: This question evaluates proficiency with shortest-path algorithms and time-dependent graph modeling, focusing on reasoning about travel times combined with periodic departure schedules and waiting-time calculations.
You are given a set of directed bus segments between stops. Each segment is represented as (from_stop, to_stop, travel_time, wait_interval). A bus on a segment departs at times 0, wait_interval, 2 * wait_interval, and so on. If a traveler reaches from_stop at time t, they may depart immediately only if t is exactly a departure time; otherwise they must wait until the next departure.
Starting from source at start_time, return the earliest possible arrival time at target. If target cannot be reached, return -1.
A correct solution should also handle important edge cases such as source == target, exact departure times, disconnected graphs, empty segment lists, and multiple segments between the same two stops.
Constraints
- 0 <= len(segments) <= 200000
- Each segment is a tuple (from_stop, to_stop, travel_time, wait_interval)
- 0 <= travel_time <= 10^9
- 1 <= wait_interval <= 10^9
- 0 <= start_time <= 10^9
- Stop names are strings
Examples
Input: ([("A", "B", 10, 5)], "A", "B", 0)
Expected Output: 10
Explanation: A bus leaves A for B at time 0, so the traveler departs immediately and arrives at time 10.
Input: ([("A", "B", 10, 5), ("B", "C", 7, 3), ("A", "C", 30, 10)], "A", "C", 6)
Expected Output: 28
Explanation: From A at time 6, the next A->B bus leaves at 10 and arrives at 20. From B at 20, the next B->C bus leaves at 21 and arrives at 28. The direct A->C route would arrive later at 40.