Reachability Between Stations in a Timed Train Schedule
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a train timetable. Each train makes one trip from a departure station to an arrival station, leaving at its departure time and arriving at its arrival time. You start at station `source`. Return whether you can reach station `destination` by taking a sequence of trains, where each train after the first departs from the station where the previous one arrived, no earlier than the previous train's arrival time.
### Function Signature
```python
def can_reach(trains: list[tuple[str, str, int, int]], source: str, destination: str) -> bool:
```
Each train is `(departure_station, arrival_station, departure_time, arrival_time)`.
### Rules
- At the start you are at `source` and can wait there as long as you like, so you can board any train that departs from `source`, whatever its departure time.
- Transfers take no time: after arriving at a station at time `t`, you can board any train that departs from that station at time `t` or later, but not one that departs before `t`.
- You may wait at any station for any length of time, take any number of trains, and pass through the same station more than once.
- A train is boarded only at its departure station and left only at its arrival station; it makes no intermediate stops.
- If `source == destination`, return `True`.
- `source` and `destination` may be stations that appear in no train.
### Constraints
- `0 <= len(trains) <= 10^5`
- Station names are non-empty strings of at most 10 letters and digits.
- `0 <= departure_time < arrival_time <= 10^9` for every train.
- Each train's departure station differs from its arrival station.
- `trains` is in no particular order and may contain identical entries.
### Examples
**Example 1**
```text
Input: trains = [("A", "Y", 1, 20), ("A", "Y", 2, 5), ("Y", "B", 6, 9)], source = "A", destination = "B"
Output: True
```
The train leaving A at 1 reaches Y at 20, too late for the train leaving Y at 6. The train leaving A at 2 reaches Y at 5, and from there the train leaving Y at 6 reaches B at 9.
**Example 2**
```text
Input: trains = [("A", "Y", 1, 20), ("A", "Y", 2, 5), ("Y", "B", 4, 9)], source = "A", destination = "B"
Output: False
```
The earliest you can be at Y is time 5, but the only train from Y to B leaves at 4.
**Example 3**
```text
Input: trains = [("A", "C", 0, 3), ("C", "D", 3, 4), ("D", "B", 2, 8), ("D", "B", 4, 7)], source = "A", destination = "B"
Output: True
```
You reach C at 3 and can board the train that leaves C at 3. You reach D at 4: the train leaving D at 2 has already gone, but the train leaving D at 4 reaches B at 7.
Overview: Given a timetable of trains, each with departure and arrival stations and times, decide whether you can travel from a source station to a destination when every connecting train must depart no earlier than you arrive. It tests graph search over time-dependent connections and careful handling of transfer timing.
Read the full Google Software Engineer interview experience this question came from
You are given a train timetable. Each train makes one trip from a departure station to an arrival station, leaving at its departure time and arriving at its arrival time. Each train is given as `(departure_station, arrival_station, departure_time, arrival_time)`.
You start at station `source`. Return `True` if you can reach station `destination` by taking a sequence of trains in which each train after the first departs from the station where the previous one arrived, no earlier than the previous train's arrival time. Otherwise return `False`.
### Rules
- At the start you are at `source` and can wait there as long as you like, so you can board any train that departs from `source`, whatever its departure time.
- Transfers take no time: after arriving at a station at time `t`, you can board any train that departs from that station at time `t` or later, but not one that departs before `t`.
- You may wait at any station for any length of time, take any number of trains, and pass through the same station more than once.
- A train is boarded only at its departure station and left only at its arrival station; it makes no intermediate stops.
- If `source == destination`, return `True`.
- `source` and `destination` may be stations that appear in no train.
### Constraints
- `0 <= len(trains) <= 10^5`
- Station names, including `source` and `destination`, are non-empty strings of at most 10 letters and digits.
- `0 <= departure_time < arrival_time <= 10^9` for every train, so every time fits in a signed 32-bit integer.
- Each train's departure station differs from its arrival station.
- `trains` is in no particular order and may contain identical entries.
### Input format by language
In Python and JavaScript each train is a 4-element sequence in the order above. In Java each train is a `java.util.List<Object>` holding two `String` station names followed by two `java.lang.Number` times. In C++ each train is a `std::tuple<std::string, std::string, int, int>`.
### Example 1
```text
Input: trains = [('A', 'Y', 1, 20), ('A', 'Y', 2, 5), ('Y', 'B', 6, 9)], source = 'A', destination = 'B'
Output: True
```
The train leaving A at 1 reaches Y at 20, too late for the train leaving Y at 6. The train leaving A at 2 reaches Y at 5, and from there the train leaving Y at 6 reaches B at 9.
### Example 2
```text
Input: trains = [('A', 'Y', 1, 20), ('A', 'Y', 2, 5), ('Y', 'B', 4, 9)], source = 'A', destination = 'B'
Output: False
```
The earliest you can be at Y is time 5, but the only train from Y to B leaves at 4.
Constraints
- 0 <= len(trains) <= 10^5
- Station names, including source and destination, are non-empty strings of at most 10 letters and digits.
- 0 <= departure_time < arrival_time <= 10^9 for every train (every time fits in a signed 32-bit integer).
- Each train's departure station differs from its arrival station.
- trains is in no particular order and may contain identical entries.
Examples
Input: ([], 'A', 'A')
Expected Output: True
Explanation: Empty timetable with source equal to destination: no train is needed, so True.
Input: ([], 'A', 'B')
Expected Output: False
Explanation: Empty timetable with distinct source and destination: nothing can be boarded, so False.
Hints
- Because you can wait anywhere for free, being at a station earlier never allows fewer onward trains than being there later.
- A train is only useful if you can be at its departure station no later than its departure time; ask what you must already know about that station when you consider the train.
- In Example 1 the first train you might notice into Y arrives too late; make sure a station's best arrival time can still improve after you have first reached it.
Community answers
Answer by danghuy.kstnbk
from heapq import heappush, heappop
def can_reach(trains, source, destination):
if source == destination:
return True
heap = []
graph = defaultdict(list)
for departure_station, arrival_station, departure_time, arrival_time in trains:
graph[departure_station].append((departure_time, arrival_time, arrival_station))
if departure_station == source:
heappush(heap, (arrival_time, arrival_station))
while heap:
curr_time, curr_station = heappop(heap)
if curr_station == destination:
return True
while graph[curr_station]:
departure_time, arrival_time, arrival_station = graph[curr_station].pop()
if departure_time >= curr_time:
heappush(heap, (arrival_time, arrival_station))
return False