Quick Overview

Solve train-schedule reachability with waiting and transfers using time-respecting graph search. The answer models earliest station arrival, preprocesses station visits, handles forward-only train routes, and explains transfer edge cases and complexity.

Determine Reachability in Train Schedule

Company: Glean

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a train schedule represented as a list of train routes. Each route is a list of station names, where the element at index `t` is the station that train visits at absolute time `t`. Every train starts operating at time `0` and stops after its last listed station. A passenger starts at station `start` at time `0`. The passenger may board any train at their current station at the current time, stay on that train to any later station on that same route, get off at any visited station, wait at a station for any amount of time, and transfer to another train that arrives later at the same station. Write `can_reach(schedule, start, destination)` to return whether the passenger can eventually reach `destination`. ### Constraints & Assumptions - `start` and `destination` appear somewhere in the schedule. - Station names are strings. - Time is discrete and equals the route index. - Waiting at a station is allowed. - Traveling backward on a route is not allowed unless another listed route later visits stations in that order. ### Clarifying Questions to Ask - Can multiple trains visit the same station at the same time? - Are all routes indexed from absolute time `0`? - Should reaching the destination at any time return true? - Is the schedule small enough for graph search over events? ### Part 1 - Model The State Space How would you model reachability with time? #### What This Part Should Cover - A state can be represented as `(station, earliest_arrival_time)`. - Because waiting is allowed, arriving earlier at a station dominates arriving later. - Need to respect route direction and train arrival times. ### Part 2 - Design The Algorithm How would you determine whether the destination is reachable? #### What This Part Should Cover - Preprocess each station to all train visits `(time, route_id, index)`. - Use a BFS or Dijkstra-like earliest-arrival search over stations. - From a reachable station at time `t`, board any train visit at that station with visit time `>= t`, then mark later stations on that route reachable at their visit times. ### Part 3 - Analyze Complexity And Edge Cases What complexity and edge cases matter? #### What This Part Should Cover - Handling waiting, transfers, multiple visits to same station, repeated stations, start equals destination, unreachable reverse direction, and large schedules. - Complexity in terms of total train visits and route lengths. ### What a Strong Answer Covers - Does not treat station connectivity as undirected. - Correctly handles waiting for later trains. - Uses earliest arrival to avoid infinite revisits. - Explains why the example `A -> B`, wait, then `B -> Z` is reachable. ### Follow-up Questions - How would you return the actual path? - How would you optimize if schedules are very large? - What if trains have arbitrary timestamps instead of index-based time? - What if routes repeat a station?

Quick Answer: Solve train-schedule reachability with waiting and transfers using time-respecting graph search. The answer models earliest station arrival, preprocesses station visits, handles forward-only train routes, and explains transfer edge cases and complexity.

You are given a train schedule represented as a list of train routes. Each route is a list of station names, where the element at index `t` is the station that train visits at absolute time `t`. Every train starts operating at time `0` and stops after its last listed station. A passenger starts at station `start` at time `0`. The passenger may board any train at their current station at the current time, stay on that train to any later station on that same route, get off at any visited station, wait at a station for any amount of time, and transfer to another train that arrives later at the same station. Implement `can_reach(schedule, start, destination)` returning a boolean: whether the passenger can eventually reach `destination`. Example: schedule = [["A", "B", "C"], ["D", "B", "E"]] can_reach(schedule, "A", "C") # True (ride train 0 to C) can_reach(schedule, "A", "E") # True (ride train 0 to B at t=1, board train 1 at B which is also there at t=1, ride to E) can_reach(schedule, "C", "A") # False (travel is forward in time only) can_reach(schedule, "A", "D") # False Key constraint: time matters. Reaching station S at time t only lets you board trains that visit S at a time >= t. You cannot board a train that already passed S earlier. Constraints & Assumptions: - `start` and `destination` both appear somewhere in the schedule. - Station names are strings; time is discrete and equals the route index. - Waiting at a station for any amount of time is allowed. - Travel on a route only goes forward (later indices); reaching a station does not let you go back to an earlier station on that same route.

Constraints

  • start and destination both appear somewhere in the schedule.
  • Station names are arbitrary strings; the same station may appear on multiple routes and at multiple times.
  • Time is discrete and equals the route index; every train starts at time 0.
  • Waiting at a station for any amount of time is allowed.
  • Travel on a route is forward-only: reaching a station does not let you reach earlier stations on the same route.

Examples

Input: ([["A", "B", "C"], ["D", "B", "E"]], "A", "C")

Expected Output: True

Explanation: Board train 0 at A (t=0) and ride to C (t=2).

Input: ([["A", "B", "C"], ["D", "B", "E"]], "A", "E")

Expected Output: True

Explanation: Ride train 0 to B (t=1); train 1 also visits B at t=1, so board it and ride to E (t=2).

Hints

  1. A plain undirected graph of stations is wrong: trains move forward in route order and time matters. Model state as (station, earliest_arrival_time).
  2. Because waiting is allowed, arriving earlier at a station dominates arriving later. Track the earliest time each station is reachable and only relax when you find a strictly earlier arrival.
  3. Preprocess each station to the list of train visits (time, route_id, index). From a reachable station at time t, you may board any visit with visit_time >= t and then ride that train to any later station on its route (arriving at that station's index time).

Loading coding console...