0

Reachability in a time-indexed train schedule

by Frontier Interview· about 3 hours ago· ⑂ 0 remixes

Question: Reachability in a time-indexed train schedule

Companies: Glean

Difficulty: Medium

Problem statement

Given train departures and arrivals with timestamps, decide whether a destination is reachable from a start station without time travel. Reported on 1point3acres' Glean bank; reconstructed in our own words.

Clarify the setup

A timetable is a list of train legs: (train_id, from_station, to_station, depart, arrive) with depart < arrive. You stand at start at time t0. Can you reach goal? Ask:

  • Can you wait at a station? Yes, as long as you like.
  • Can you board a leg that departs at the exact minute you arrive? Say yes for part 1 (arrive <= depart). Part 2 adds a minimum transfer time when changing trains.
  • Deadline? "Reach goal by time T" is the same question as "what is the earliest arrival", compared with T. Compute the earliest arrival; it answers both.
  • Return the route? Part 2.
  • Size. A national timetable has around a million legs per day.

Approach

Plain graph search over stations is wrong: an edge is only usable if you are at its station before it departs, so reachability depends on time. Two correct approaches:

Time-dependent Dijkstra. Nodes are stations; the label is the earliest arrival time; relaxing a station scans its departures at or after that time. Correct, O(E log V) with a heap.

Connection scan (simpler and usually faster). Sort all legs by departure time once. Keep earliest[station], initially infinity except earliest[start] = t0. Scan legs in departure order: a leg is usable if earliest[from] <= depart; if so, earliest[to] = min(earliest[to], arrive).

Why one pass is enough: when you reach a leg in the scan, every leg that could get you to its from station in time departs earlier (it must arrive by depart, and it departs before it arrives), so it has already been scanned. That is the invariant to state.

Stop early once the scan passes the deadline, or once the current leg departs after earliest[goal] (nothing later can improve it).

Part 2: transfers and the route. With a minimum transfer time m, staying on the same train costs nothing, but changing trains needs m minutes. Track per train whether you are already aboard (on_train[train_id]). A leg is usable if you are on that train already, or if earliest[from] + m <= depart (or earliest[from] <= depart at the start station, where no transfer is involved). To return the route, remember for each station the leg that set its earliest arrival and, for each train, the leg where you boarded it, and walk back from the goal.

Code

from typing import Dict, List, Optional, Tuple

Leg = Tuple[str, str, str, int, int]  # (train, from, to, depart, arrive)
INF = float("inf")


def earliest_arrival(legs: List[Leg], start: str, t0: int, goal: str) -> float:
    earliest: Dict[str, float] = {start: t0}
    for train, frm, to, dep, arr in sorted(legs, key=lambda l: l[3]):
        if dep > earliest.get(goal, INF):
            break                                       # nothing later can improve
        if earliest.get(frm, INF) <= dep and arr < earliest.get(to, INF):
            earliest[to] = arr
    return earliest.get(goal, INF)


def can_reach(legs: List[Leg], start: str, t0: int, goal: str, deadline: float = INF) -> bool:
    return earliest_arrival(legs, start, t0, goal) <= deadline


def route_with_transfers(legs: List[Leg], start: str, t0: int, goal: str,
                         transfer: int) -> Optional[Tuple[int, List[Leg]]]:
    """Earliest arrival and the legs taken, with `transfer` minutes to change trains."""
    if start == goal:
        return t0, []
    earliest: Dict[str, float] = {start: t0}
    arrived_by: Dict[str, Leg] = {}               # leg that set earliest[station]
    boarded: Dict[str, Leg] = {}                  # train -> first leg we could take on it
    for leg in sorted(legs, key=lambda l: (l[3], l[4])):
        train, frm, to, dep, arr = leg
        if dep > earliest.get(goal, INF):
            break
        if train not in boarded:
            ready = earliest.get(frm, INF)
            if frm != start or ready != t0:
                ready += transfer                     # changing trains takes time
            if ready > dep:
                continue
            boarded[train] = leg
        if arr < earliest.get(to, INF):
            earliest[to] = arr
            arrived_by[to] = leg
    if goal not in earliest:
        return None
    path: List[Leg] = []
    station = goal
    while station != start:
        last = arrived_by[station]
        train = last[0]
        # ride this train backwards to where we boarded it
        ride = [l for l in sorted(legs, key=lambda l: l[3])
                if l[0] == train and boarded[train][3] <= l[3] <= last[3]]
        path = ride + path
        station = boarded[train][1]
    return int(earliest[goal]), path

The route walk assumes a train's legs form one path (a train does not visit a station twice), which holds for real timetables. Rebuilding ride scans the legs again; precomputing legs per train sorted by time makes it O(legs on the route).

Complexity

  • Sorting: O(C log C) for C legs, done once per timetable (keep it sorted and reuse it for every query).
  • Each query: O(C) scan, usually far less with the early exit.
  • A million legs per day scan in tens of milliseconds in a compiled language; in Python, about a second without the early exit. Precomputing per-station departure lists and starting the scan at t0 (binary search) cuts most of it.

Test cases

LEGS = [
    ("T1", "A", "B", 900, 1000),
    ("T1", "B", "C", 1005, 1100),
    ("T2", "B", "D", 1000, 1030),   # departs as T1 arrives at B
    ("T3", "D", "C", 1040, 1050),
    ("T4", "C", "E", 800, 850),     # too early to be useful
    ("T5", "A", "E", 1200, 1300),
]


def test_earliest_arrival_and_deadline():
    assert earliest_arrival(LEGS, "A", 850, "C") == 1050   # via B -> D -> C
    assert earliest_arrival(LEGS, "A", 850, "E") == 1300
    assert can_reach(LEGS, "A", 850, "C", deadline=1060)
    assert not can_reach(LEGS, "A", 850, "C", deadline=1049)


def test_no_time_travel():
    assert earliest_arrival(LEGS, "A", 950, "C") == float("inf")   # T1 already left
    assert earliest_arrival([("X", "A", "B", 10, 20), ("Y", "B", "C", 15, 25)], "A", 0, "C") == float("inf")


def test_start_is_goal_and_unknown_station():
    assert earliest_arrival(LEGS, "A", 850, "A") == 850
    assert earliest_arrival(LEGS, "Z", 0, "A") == float("inf")

def test_transfer_time_changes_the_route():
    best, path = route_with_transfers(LEGS, "A", 850, "C", transfer=0)
    assert best == 1050 and [l[0] for l in path] == ["T1", "T2", "T3"]
    best, path = route_with_transfers(LEGS, "A", 850, "C", transfer=5)
    assert best == 1100 and [l[0] for l in path] == ["T1", "T1"]     # stay aboard T1


def test_staying_on_a_train_needs_no_transfer():
    legs = [("T", "A", "B", 0, 10), ("T", "B", "C", 10, 20)]
    assert route_with_transfers(legs, "A", 0, "C", transfer=30) == (20, legs)
    assert route_with_transfers(legs, "A", 1, "C", transfer=0) is None


def test_matches_simple_scan_without_transfers():
    import random
    rng = random.Random(6)
    stations = "ABCDEF"
    for _ in range(200):
        legs = []
        for i in range(25):
            a, b = rng.sample(stations, 2)
            dep = rng.randint(0, 100)
            legs.append((f"T{i}", a, b, dep, dep + rng.randint(1, 20)))
        got = route_with_transfers(legs, "A", 0, "F", transfer=0)
        want = earliest_arrival(legs, "A", 0, "F")
        assert (got is None and want == float("inf")) or got[0] == want

Follow-ups

  1. Latest departure. "When is the latest I can leave A and still arrive by 18:00?" Scan legs by arrival time in reverse, tracking latest[station] from the goal backwards.
  2. Fewest transfers. Pareto-optimal journeys (earliest arrival for each number of transfers) need a label per transfer count: run the scan in rounds (RAPTOR-style), round k allowing k trains.
  3. Footpaths. Walking between nearby stations adds edges with a duration rather than a timetable; relax them whenever a station's earliest arrival improves.
  4. Delays. Real-time delays change depart and arrive of some legs. Keep the sorted order up to date incrementally, or re-sort only the affected window, and recompute affected queries.
  5. Many queries. Precompute per station the departures sorted by time; for repeated queries from popular stations, cache profiles (earliest arrival as a function of departure time).

Interviewer expectations

Mid-level (L4)

  • Recognizes that time makes plain BFS wrong and builds a correct search (time-dependent Dijkstra or connection scan).
  • Handles waiting, same-minute connections and unreachable goals.
  • Tests a case where a shortcut exists only in the wrong time order.

Senior (L5)

  • Uses the connection scan with the invariant that explains why one pass suffices, plus an early exit.
  • Adds transfer times correctly: free when staying on the same train.
  • Reconstructs the route.

Staff (L6+)

  • Covers latest departure, fewest transfers with rounds, footpaths and real-time delays.
  • Plans for query volume: sorted departures per station, binary search to the start time, caching.
  • Discusses the trade-offs between connection scan, time-dependent Dijkstra and round-based methods.

Sign in to comment, vote or remix.