How should I practice Reachable Nodes in a Directed Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Sofi online assessment problems in FastPrep.

Is Reachable Nodes in a Directed Graph associated with Sofi?

FastPrep tags this as a Sofi coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Graph

Reachable Nodes in a Directed Graph

Learn this problem

● MediumSofiFULLTIMEONSITE INTERVIEW

Problem statement

🐒 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.