Katkat
Back

Find Earliest Train Route

GleanMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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:

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:

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