← SoFi Interview InsightsSoftware Engineer

SoFi·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Got a graph traversal problem at SoFi that was dressed up as a choose-your-own-adventure story, which honestly threw me for a second before I realized it was just reachability in a directed graph. Solid technical screen, nothing behavioral, just the one meaty problem.

Questions Asked (1)

Q1

You're given a choose-your-own-adventure story modeled as a graph where every choice node has options pointing to other nodes or ending nodes. Unlike a typical path problem, you must traverse ALL options at every node. Find the complete set of reachable ending nodes from the start node, handle cycles, and analyze the time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The story framing tripped me up at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the story as a directed graph and perform a full traversal (DFS or BFS) from the start node, visiting every node and following all outgoing edges. Use a visited set to avoid infinite loops from cycles, and collect nodes that are endings. Analyze complexity in terms of V (nodes) and E (edges), noting that each node and edge is processed once.

Pro tip: Explicitly state that you will treat the graph as potentially cyclic and use a visited set to ensure termination; this shows you anticipate edge cases and think about correctness before coding.

1. Clarify the problem and graph representation

Confirm that every node must be explored, endings are terminal nodes, and the graph may have cycles. Ask about input format (adjacency list, etc.) and whether endings are distinct from regular nodes.

2. Choose traversal strategy

Select DFS (recursive or iterative) or BFS. Emphasize that both work; DFS is often simpler for full exploration, but BFS can be used if you want to process level by level.

3. Implement traversal with cycle handling

Use a visited set to mark nodes as you encounter them. For each node, if it's an ending, add to results; otherwise, recursively or iteratively visit all unvisited neighbors.

4. Collect and return ending nodes

Maintain a set or list of ending nodes encountered during traversal. Ensure no duplicates and that all reachable endings are included.

5. Analyze time and space complexity

Time: O(V + E) because each node and edge is visited once. Space: O(V) for the visited set and recursion stack (DFS) or queue (BFS), plus O(E) for the graph storage if not given.

Key Points to Mention

  • Graph traversal algorithms (DFS/BFS) and their trade-offs
  • Cycle detection and avoidance using a visited set
  • Time complexity O(V + E) and space complexity O(V)
  • Handling of disconnected components (though not needed here, it's good to mention)
  • Edge cases: start node is an ending, no endings, self-loops, multiple edges
  • Choice of data structures: adjacency list vs. adjacency matrix and their impact on complexity

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.