← SoFi Interview InsightsSoftware Engineer

SoFi·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Got a coding question at SoFi for a software engineering role that was essentially a graph traversal problem dressed up as a choose-your-own-adventure scenario. Pretty interesting framing, though the core of it was just DFS with memoization once you stripped away the story wrapper.

Questions Asked (1)

Q1

Given a choose-your-own-adventure graph structure with choice nodes, option edges, and a set of ending nodes, find all endings reachable from the start node by traversing every possible single path through the graph.

Algorithms & Data Structures
Author's notes

The story framing threw me off for longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the graph structure and constraints, then choose between DFS and BFS for traversal. Use a visited set to avoid infinite loops and collect all ending nodes reached.

Pro tip: Mention that if the graph is a DAG, you can use memoization to cache reachable endings from each node, improving efficiency for multiple queries.

1. Clarify the problem

Ask about graph properties: directed/undirected, cycles, multiple edges, and whether 'single path' means simple path (no repeated nodes) or any path. Confirm if endings are unique or can be reached multiple times.

2. Choose traversal algorithm

Decide between DFS (recursive or iterative) and BFS. DFS is natural for exploring all paths; BFS can also work but may use more memory. Consider iterative DFS to avoid recursion depth limits.

3. Handle cycles and visited nodes

Use a visited set to track nodes on the current path (for simple paths) or globally visited nodes (to avoid reprocessing). If cycles exist, ensure termination by not revisiting nodes in the current path.

4. Collect and return endings

When an ending node is reached, add it to a result set (to avoid duplicates). Continue traversal until all paths are explored. Return the set of reachable endings.

5. Analyze complexity and edge cases

Discuss time complexity O(V+E) for DAGs or O(V+E) per path for cyclic graphs, and space complexity O(V) for recursion/visited. Mention edge cases: no endings, start is an ending, disconnected graph.

Key Points to Mention

  • Graph representation: adjacency list vs. adjacency matrix, and how to store choice nodes and option edges.
  • Traversal algorithm: DFS vs. BFS, and why DFS is often preferred for path exploration.
  • Cycle detection and handling: using a visited set or recursion stack to avoid infinite loops.
  • Path definition: whether 'single path' means simple path (no repeated nodes) or any path, which affects visited set usage.
  • Ending collection: using a set to deduplicate endings and returning all reachable endings.
  • Complexity analysis: time and space complexity, and potential optimizations like memoization for DAGs.

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