Reachable Nodes in a Directed Graph

🐒 FastPrep source match note: This practice version is based on a reported SoFi Staff Engineer onsite question last seen on July 3, 2026. The original asked candidates to return reachable Vertex objects from a directed graph. FastPrep uses unique vertex ids and an adjacency-list input so the same traversal task can run in the workspace; the coding goal and interview discussion path are a 90%+ match to the reported prompt and backed by the provided source screenshot. 🐝
You are given a directed graph. In the original interview prompt, the graph is represented by Vertex objects, and each vertex contains a collection of outgoing neighbors.
In this executable FastPrep version, each vertex is represented by a unique string id. The input graph is an adjacency list where each row starts with a vertex id, followed by that vertex's outgoing neighbors. A row with only one value represents a vertex with no outgoing neighbors.
Implement the function reachableNodes.
The function should return all vertices that can be reached from start, including start itself.
The graph may contain cycles. Your implementation must avoid visiting the same vertex repeatedly and must not get stuck in an infinite loop.
The returned collection does not need to be in any specific order.
Clarifications / Corner Cases
The graph is directed.
The result should include the starting vertex.
The graph may contain cycles or self-loops.
The graph may be disconnected.
A vertex may have no outgoing neighbors.
The output order does not matter.
Assume start is not null.
Assume each vertex can be uniquely identified, either by object identity or by a unique id/name.
Follow-up / Interview Discussion
How would you implement this using DFS?
How would you implement this using BFS?
What state is necessary to prevent repeated work or infinite loops?
Is a parent map necessary for this problem? Why or why not?
What can go wrong with recursive DFS on a very deep graph?
When would BFS be preferable to DFS?
If the graph has thousands of vertices in a long chain, what implementation choice is safer in Java?

Function
reachableNodes(graph: String[][], start: String) → String[]

Examples
Example 1
graph = [["A", "B"], ["B", "C", "D"], ["C"], ["D", "E"], ["E", "B"]]
start = "A"
return = ["A", "B", "C", "D", "E"]
Given the directed graph:
A -> B
B -> C, D
D -> E
E -> B
Starting from A, we can reach B. From B, we can reach C and D. From D, we can reach E. From E, we go back to B, but B has already been visited.
One valid return value is [A, B, C, D, E].
Example 2
graph = [["A", "B"], ["B"], ["C", "D"], ["D"]]
start = "A"
return = ["A", "B"]
C and D exist in the graph, but they are not reachable from A.
Example 3
graph = [["A", "A"]]
start = "A"
return = ["A"]
A has a self-cycle. The algorithm should include A once and stop.

Constraints
1 <= number of vertices <= 100,000
0 <= number of directed edges <= 300,000
The graph may be sparse, dense, shallow, or very deep.
Only vertices reachable from start need to be returned.

The trick is a visited set plus a traversal. Build a map from vertex id to its neighbor list from the rows, then run BFS or iterative DFS from start. Mark a vertex visited when you push it, not when you pop it, so duplicates never enter the queue. That handles cycles and self-loops like [A, A] for free. The common pitfall is recursive DFS. The constraints allow 100,000 vertices in a long chain, so recursion can overflow the stack. Use an explicit stack or a queue. Other traps: vertices with no row in the map (treat as no neighbors), and forgetting to include start itself. You don't need a parent map, since you only return reachable nodes, not paths. Complexity is O(V + E) time and space. If you freeze on the iterative loop during the live OA, StealthCoder is the hedge that shows you a clean version.

StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.