Paths in Maze That Lead to Same Room

Paths in Maze That Lead to Same Room

What is this problem about?

The Paths in Maze That Lead to Same Room problem asks you to count pairs of rooms (a, b) such that there exists a third room c that is reachable from both a and b (i.e., a→c and b→c via directed edges). This coding problem finds pairs of rooms sharing a common reachable room, using graph cycle detection or connectivity analysis. The graph interview pattern is the core.

Why is this asked in interviews?

Salesforce and Google ask this to test graph connectivity reasoning — specifically, finding "common successors" for all pairs of nodes. With small graph sizes, the approach can involve DFS reachability sets or direct cycle analysis.

Algorithmic pattern used

DFS reachability + common successor counting. For each node, compute the set of nodes reachable from it via directed edges. For each pair (a, b), if their reachable sets share at least one common node c (other than a and b themselves), count this pair. For undirected graphs: find all triangles. For directed 3-cycles (a→c→b, a→b): count valid ordered triples.

Example explanation

Rooms: 1,2,3. Edges: 1→2, 1→3, 2→3, 3→1. Room 1 reaches: {2,3}. Room 2 reaches: {3,1}. Room 3 reaches: {1,2}. Pairs with common reachable room: (1,2) both reach 3 ✓. (1,3) both reach 2 ✓. (2,3) both reach 1 ✓. Count = 3 pairs.

Common mistakes candidates make

• Counting directed pairs as undirected (must distinguish a→c and b→c vs other arrangements).
• Using full reachability computation when direct neighbors suffice for triangles.
• Not excluding c=a or c=b from shared reachable rooms.
• Double-counting ordered vs unordered pairs.

Interview preparation tip

"Paths leading to same destination" problems reduce to: find pairs of nodes sharing a common successor/neighbor. For undirected graphs, this is triangle counting — count triples (a,b,c) where all three are connected, then adjust for ordering. Practice triangle counting algorithms and "common neighbor" problems on graphs. These appear in social network analysis and collaborative filtering interviews.