Check connectivity between two subway stations
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a description of subway stations A, B, C, D, E, ... as a graph. For each station, you are told which other stations it directly connects to (e.g., an adjacency list/map).
Write a function that, given two station names start and end, returns whether it is possible to travel from start to end by following one or more connections (i.e., whether a path exists).
Assume station names are strings. If a station is not present in the map, treat it as having no outgoing connections.
Additionally, write a few test cases for your function (including cases with cycles, disconnected components, start==end, and missing stations).
Quick Answer: This problem evaluates graph connectivity and traversal concepts—specifically reasoning about adjacency representations, path existence, cycles, disconnected components, and missing-node edge cases—within the Coding & Algorithms domain at an implementation-level (medium) abstraction.
You are given a subway network as an adjacency map where each key is a station name and its value is a list of stations that can be reached directly from it. Write a function that returns whether it is possible to travel from a given start station to a given end station by following these connections.
Treat the graph exactly as listed: you may only travel from a station to the stations in its adjacency list. If a connection is bidirectional, both directions must appear in the map. If a station is missing from the map, treat it as having no outgoing connections. A station is considered reachable from itself, even without taking any connections.
The graph may contain cycles.
Constraints
- 0 <= number of stations in the map <= 100000
- 0 <= total number of listed connections <= 200000
- Station names are strings
- A station may appear in a neighbor list even if it is not a key in the map; such a station has no outgoing connections
Examples
Input: ({'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': ['E'], 'E': []}, 'A', 'E')
Expected Output: True
Explanation: One valid path is A -> B -> D -> E.
Input: ({'A': ['B'], 'B': ['C'], 'C': ['A', 'D'], 'D': []}, 'A', 'D')
Expected Output: True
Explanation: The graph contains a cycle A -> B -> C -> A, but D is still reachable through A -> B -> C -> D.
Input: ({'A': ['B'], 'B': [], 'C': ['D'], 'D': []}, 'A', 'D')