Train Schedule Reachability | Dataford Interview Questions

Glean may need to determine whether a user can travel between offices using a fixed train schedule. Given a starting station, destination, earliest departure time, and train trips, return whether the destination is reachable through zero or more connections.

Each trip is represented as [from_station, to_station, departure_time, arrival_time]. A passenger can board a trip only if they are already at from_station and departure_time >= their arrival time at that station. Times are integer minutes from the start of the day, and every trip arrives no earlier than it departs.

Formal Specification

Implement can_reach(start, destination, start_time, trips), where start and destination are strings, start_time is an integer, and trips is a list of four-element lists. Return a boolean. The passenger is considered to have reached the destination immediately when start == destination.

Constraints

1 <= len(trips) <= 10^5
Station names are non-empty strings
0 <= start_time, departure_time, arrival_time <= 10^9
departure_time <= arrival_time for every trip
A passenger may wait at a station between trains

Function Signature

def can_reach(start, destination, start_time, trips):

Your question is Train Schedule Reachability. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

1 <= len(trips) <= 10^5
Station names are non-empty strings
0 <= start_time, departure_time, arrival_time <= 10^9
departure_time <= arrival_time for every trip
A passenger may wait at a station between trains

Function Signature

def can_reach(start, destination, start_time, trips):

Your question is Train Schedule Reachability. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.