← SoFi Interview Insights

SoFi·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

SoFi software engineer interview with a graph traversal problem that sounds deceptively simple until you're actually implementing it. The problem was framed as a choose-your-own-adventure story, which was a cute wrapper but made it easy to overthink the structure.

Questions Asked (1)

Q1

Given a choose-your-own-adventure story represented as a graph of choices and options, find all endings reachable from the starting node by following valid paths through the graph.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The story framing threw me off for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the graph representation (directed, possibly cyclic) and define what constitutes an 'ending' (e.g., nodes with no outgoing edges). Then propose a traversal algorithm (DFS or BFS) with a visited set to handle cycles and collect all reachable terminal nodes.

Pro tip: Mention that you'd first check for cycles and decide whether to treat revisiting a node as a dead end or continue exploring; this shows you consider edge cases and real-world story graphs that may loop.

1. Clarify the problem

Ask questions to confirm the graph type (directed/undirected), whether cycles are possible, and how endings are defined (e.g., nodes with no outgoing edges).

2. Choose traversal strategy

Select DFS or BFS based on requirements; DFS is simpler for recursion and path tracking, while BFS can find shortest paths to endings if needed.

3. Handle cycles and visited nodes

Use a visited set to avoid infinite loops; decide whether to mark nodes globally or per path, and explain the trade-offs.

4. Collect and return endings

During traversal, identify terminal nodes and add them to a result set; ensure uniqueness if multiple paths lead to the same ending.

5. Analyze complexity and edge cases

Discuss time and space complexity (O(V+E) for traversal), and mention edge cases like empty graph, start node being an ending, or disconnected components.

Key Points to Mention

  • Graph representation: adjacency list vs. adjacency matrix, and why adjacency list is efficient for sparse graphs.
  • Cycle detection and handling: using a visited set to prevent infinite loops, and whether to treat cycles as dead ends.
  • Traversal algorithms: DFS (recursive/iterative) vs. BFS, and their trade-offs for this problem.
  • Definition of an ending: nodes with out-degree zero, or explicitly marked terminal nodes.
  • Time and space complexity: O(V+E) time, O(V) space for visited set and recursion stack.
  • Edge cases: empty graph, start node is an ending, multiple paths to same ending, and disconnected endings.

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