Robinhood·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Robinhood SWE interview with a graph propagation problem that starts simple but has a neat optimization hiding in it. The follow-up is where things get interesting and probably where most people either shine or quietly fall apart.

Questions Asked (1)

You're given a directed acyclic graph as an edge list and a root node. A trigger starts at the root and propagates to all reachable descendants. For each node in a target set, how many times does it get triggered? Then optimize it.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went with DFS first which is the obvious move, just count how many times you visit each node.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: in a DAG, a node is triggered if there is a path from the root to it. The number of times a node is triggered equals the number of distinct paths from the root to that node. Use dynamic programming (topological order) to compute path counts efficiently, then optimize by only computing for target nodes or using memoization.

Pro tip: Mention that the number of paths can be exponential, so use modulo or big integers as needed. Also, discuss trade-offs between precomputing all nodes vs. computing on-demand for targets.

1. Clarify the problem

Confirm that 'triggered' means reachable from root, and the count is the number of distinct paths from root to the node. Ask about constraints: graph size, target set size, and whether counts can be large.

2. Naive approach

For each target, perform DFS/BFS from root to count paths. This is exponential in worst case and inefficient for large graphs.

3. Dynamic programming with topological order

Compute path counts for all nodes in topological order: initialize root count to 1, then for each node, add its count to all outgoing neighbors. This is O(V+E) time and space.

4. Optimize for target set

If only a few targets, consider reverse graph and memoized DFS from targets to root, or prune nodes not on paths to targets. Discuss trade-offs between precomputation and on-demand.

5. Handle large counts and edge cases

Use modulo if counts can be huge, or big integers. Handle unreachable targets (count 0), root in target set (count 1), and multiple edges between same nodes (count each edge as separate path).

Key Points to Mention

Topological sort is essential for DP on DAGs.
Path counting is equivalent to number of distinct paths from root.
Time complexity: O(V+E) for full DP, space O(V+E).
Optimization: compute only for targets using reverse graph and memoization.
Large counts: use modulo or big integers.
Edge cases: unreachable nodes, root as target, parallel edges.

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