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).
Overview: 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.
Hints
- This is a graph reachability problem. Try exploring from the start station using DFS or BFS.
- Keep a visited set so you do not get stuck in cycles by revisiting the same station repeatedly.
Community answers
Answer by moreanuj1307
Try solving this problem using DFS graph traversal.
def path_exists(graph, start, end):
visited = set()
def dfs(node):
if node == end:
return True
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
if dfs(neighbor):
return True
return False
return dfs(start)
def run_tests():
graph = {
"A": ["B"],
"B": ["C"],
"C": ["A"],
"D": ["E"],
"E": [],
"F": []
}
assert path_exists(graph, "A", "C") == True # cycle
assert path_exists(graph, "A", "E") == False # disconnected
assert path_exists(graph, "D", "E") == True # direct edge
assert path_exists(graph, "F", "F") == True # start == end
assert path_exists(graph, "X", "E") == False # missing start
assert path_exists(graph, "A", "X") == False # missing end
assert path_exists(graph, "X", "X") == True # same start/end, missing node
print("All tests passed.")
run_tests()