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 Glean.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Glean during technical interviews.

Find Earliest Train Route | Glean Coding Question

Find Earliest Train Route

Company: Glean

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a discrete train timetable and need to find a valid route through the train network. Each train has an itinerary represented as a sequence of stops: ```text train_id -> [(station, time), (station, time), ...] ``` Times are integer minutes, and consecutive stops for a train occur at increasing times. A train can be boarded at a station at the exact time it is present there. Given: - A list of train itineraries. - A start station and start time. - A destination station. Part 1: Return the earliest time at which a passenger can reach the destination. Movement rules: - At any station and time, the passenger may wait until the next minute. - If one or more trains are present at the current station and time, the passenger may board any of them. - If the passenger is on a train, they may stay on that train to its next stop. - At a stop, the passenger may get off and transfer to another train that is present at the same station and time. - A valid solution should avoid infinite search over time. A common approach is to build an index like: ```text (station, time) -> list of train_ids present there ``` and run BFS or shortest-path search over time-expanded states. Part 2: Extend the solution so it can print the full route, including the sequence of stations, times, train IDs used, waits, and transfers.

Quick Answer: This question evaluates a candidate's ability to model and search time-dependent transit networks, combining temporal graph reasoning, state-space search, and path reconstruction for itinerary reporting.

Part 1: Earliest Arrival Time in a Train Timetable

You are given a list of train itineraries. Each itinerary is a pair `(train_id, stops)`, where `stops` is a list of `(station, time)` pairs in strictly increasing time order for that train. A passenger starts at `start_station` at integer minute `start_time` and wants to reach `destination` as early as possible. Rules: - The passenger may wait at any station for any number of minutes. - A train may be boarded at a station at the exact time it is present there. - Once on a train, the passenger may stay on it through its later stops. - At a stop, the passenger may get off and transfer to another train that is present at the same station and time. Return the earliest time the passenger can reach `destination`, or `-1` if it is impossible. A good way to avoid infinite search over time is to work only with timetable events that actually appear in the input, such as unique `(station, time)` pairs.

Constraints

1 <= total number of stop occurrences across all trains <= 200000
Each train itinerary has strictly increasing times
Station names and train IDs are strings
Times are integers in the range 0 to 10^9
A train itinerary may contain one stop

Examples

Input: ([('T1', [('A', 0), ('B', 5)]), ('T2', [('B', 5), ('D', 8)]), ('T3', [('A', 2), ('D', 10)])], 'A', 0, 'D')

Expected Output: 8

Explanation: Take T1 from A to B, transfer immediately to T2 at time 5, and arrive at D at time 8.

Input: ([('T1', [('A', 3), ('C', 7)]), ('T2', [('A', 1), ('B', 4)])], 'A', 0, 'C')

Expected Output: 7

Explanation: The passenger can wait at A until time 3 and then take T1 directly to C.

Input: ([('T1', [('A', 0), ('B', 5)]), ('T2', [('B', 7), ('C', 9)])], 'A', 0, 'C')

Expected Output: 9

Explanation: Ride to B at time 5, wait until time 7, then take T2 to C.

Input: ([('T1', [('B', 1), ('C', 2)])], 'A', 0, 'C')

Expected Output: -1

Explanation: No train ever appears at the start station A.

Input: ([], 'A', 4, 'A')

Expected Output: 4

Explanation: Edge case: the passenger already starts at the destination.

Hints

Think of each unique scheduled `(station, time)` as a graph node.
Add edges for waiting to the next scheduled time at the same station, and edges for moving to the next stop on the same train.

Part 2: Reconstruct the Earliest Train Route

You are given the same train timetable as in Part 1. This time, instead of returning only the earliest arrival time, return one full earliest route. Each itinerary is a pair `(train_id, stops)`, where `stops` is a list of `(station, time)` pairs in strictly increasing time order. The passenger starts at `start_station` at `start_time` and wants to reach `destination` as early as possible. Rules: - The passenger may wait at any station for any number of minutes. - A train may be boarded at the exact time it is present at the station. - The passenger may stay on the same train through later stops. - The passenger may transfer to another train if both are present at the same station and time. Return a route object with: - the earliest `arrival_time` - a chronological list of `steps` Use these step formats: - `{'action': 'start', 'station': ..., 'time': ...}` - `{'action': 'wait', 'station': ..., 'from_time': ..., 'to_time': ...}` - `{'action': 'transfer', 'station': ..., 'time': ..., 'from_train': ..., 'to_train': ...}` - `{'action': 'ride', 'train_id': ..., 'from_station': ..., 'from_time': ..., 'to_station': ..., 'to_time': ...}` Consecutive waits at the same station should be merged into one wait step. Consecutive ride segments on the same train should be merged into one ride step. If multiple earliest routes exist, any one of them is acceptable. Return `None` if the destination is unreachable.

Constraints

1 <= total number of stop occurrences across all trains <= 200000
Each train itinerary has strictly increasing times
Station names and train IDs are strings
Times are integers in the range 0 to 10^9
A train itinerary may contain one stop
If several earliest routes exist, any one is acceptable

Examples

Input: ([('T1', [('A', 0), ('B', 5), ('C', 9)])], 'A', 0, 'C')

Explanation: A single train is used for the entire journey, so the two ride segments are merged into one ride step.

Input: ([('T1', [('A', 0), ('B', 5)]), ('T2', [('B', 5), ('D', 8)])], 'A', 0, 'D')

Expected Output: {'arrival_time': 8, 'steps': [{'action': 'start', 'station': 'A', 'time': 0}, {'action': 'ride', 'train_id': 'T1', 'from_station': 'A', 'from_time': 0, 'to_station': 'B', 'to_time': 5}, {'action': 'transfer', 'station': 'B', 'time': 5, 'from_train': 'T1', 'to_train': 'T2'}, {'action': 'ride', 'train_id': 'T2', 'from_station': 'B', 'from_time': 5, 'to_station': 'D', 'to_time': 8}]}

Explanation: The transfer happens immediately at B at time 5.

Input: ([('T1', [('A', 3), ('C', 7)])], 'A', 0, 'C')

Expected Output: {'arrival_time': 7, 'steps': [{'action': 'start', 'station': 'A', 'time': 0}, {'action': 'wait', 'station': 'A', 'from_time': 0, 'to_time': 3}, {'action': 'ride', 'train_id': 'T1', 'from_station': 'A', 'from_time': 3, 'to_station': 'C', 'to_time': 7}]}

Explanation: The passenger must wait at the start station before boarding.

Input: ([('T1', [('A', 0), ('B', 5)]), ('T2', [('B', 7), ('C', 9)])], 'A', 0, 'C')

Expected Output: {'arrival_time': 9, 'steps': [{'action': 'start', 'station': 'A', 'time': 0}, {'action': 'ride', 'train_id': 'T1', 'from_station': 'A', 'from_time': 0, 'to_station': 'B', 'to_time': 5}, {'action': 'wait', 'station': 'B', 'from_time': 5, 'to_time': 7}, {'action': 'transfer', 'station': 'B', 'time': 7, 'from_train': 'T1', 'to_train': 'T2'}, {'action': 'ride', 'train_id': 'T2', 'from_station': 'B', 'from_time': 7, 'to_station': 'C', 'to_time': 9}]}

Explanation: This route includes both an intermediate wait and a transfer.

Input: ([('T1', [('B', 1), ('C', 2)])], 'A', 0, 'C')

Expected Output: None

Explanation: Edge case: no route starts from station A, so the destination is unreachable.

Hints

Solve the earliest-arrival problem on `(station, time)` nodes, but also store a parent pointer and the edge type used to reach each node.
After reconstructing the path, merge consecutive wait steps and same-train ride steps, then insert transfer steps whenever the train ID changes.

Quick Overview

This question evaluates a candidate's ability to model and search time-dependent transit networks, combining temporal graph reasoning, state-space search, and path reconstruction for itinerary reporting.