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 Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Compute Earliest Bus Arrival | Apple Coding Question

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.

Input: ([("S", "A", 5, 4), ("A", "T", 5, 5), ("S", "T", 20, 1)], "S", "T", 0)

Expected Output: 10

Explanation: Going S->A arrives at time 5, and A->T departs exactly at time 5, so the total arrival time is 10. The direct route arrives at 20.

Input: ([("A", "B", 3, 2), ("C", "D", 4, 1)], "A", "D", 1)

Expected Output: -1

Explanation: There is no path from A to D, so the destination is unreachable.

Input: ([], "X", "X", 7)

Expected Output: 7

Explanation: If the source and target are the same, the traveler is already there at the starting time.

Input: ([("A", "B", 100, 1), ("A", "B", 3, 10)], "A", "B", 9)

Expected Output: 13

Explanation: The first segment can be taken immediately and arrives at 109. The second leaves at time 10 and arrives at 13, which is earlier.

Hints

Model the stops as nodes in a directed graph. The tricky part is that the cost of taking an edge depends on the time you arrive at its starting node.
A min-heap shortest-path algorithm works here if, for each edge, you compute the next departure time using modulo arithmetic.

Quick Overview

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.