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 that is at their current station at the current time,
- stay on that train to any later station on the same route,
- get off at any visited station,
- wait at a station for any amount of time,
- transfer to another train that arrives at that station at a later time.
Write a function `can_reach(schedule, start, destination)` that returns whether the passenger can eventually reach `destination`.
Assumptions:
- `start` and `destination` both appear somewhere in the schedule.
- Station names are strings.
Example:
`schedule = [["A", "B", "C"], ["D", "B", "E"]]`
Expected results:
- `can_reach(schedule, "A", "C") -> true`
- `can_reach(schedule, "A", "E") -> true`
- `can_reach(schedule, "C", "A") -> false`
- `can_reach(schedule, "A", "D") -> false`
Important edge case:
`schedule = [["A", "B", "C", "D", "E"], ["O", "B", "G", "H", "Z"]]`
`can_reach(schedule, "A", "Z") -> true`
Explanation: the passenger can ride the first train from `A` to `B`, get off at time `1`, wait at `B`, then board the second train when it arrives at `B` and continue to `Z`.
Quick Answer: This question evaluates understanding of time-dependent graph reachability and state-space modeling, focusing on representing temporal constraints, transfers, and waiting within train routes.