← Uber Interview InsightsSoftware Engineer

Uber·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Uber coding round, graph problem that looks clean on the surface but has a few ways to go wrong. Nothing too surprising if you've done graph traversal before, but the sorting requirement at the end is easy to forget under pressure.

Questions Asked (1)

Q1

Given a directed graph, find all nodes from which every possible path eventually leads to a terminal node (a node with no outgoing edges). Return a sorted list of these safe nodes.

Algorithms & Data Structures
Author's notes

I went with DFS and three-color marking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding nodes that are not part of any cycle and can only reach terminal nodes. Use a reverse graph and topological sort (Kahn's algorithm) to iteratively remove nodes with outgoing edges to non-safe nodes, or use DFS with cycle detection and memoization to mark safe nodes.

Pro tip: Clarify edge cases upfront, such as empty graph, self-loops, and multiple components. Mention that the reverse graph approach naturally handles cycles and is O(V+E), which is optimal.

1. Understand the problem

Restate the definition: a safe node is one where every path from it eventually reaches a terminal node (no outgoing edges). Note that nodes in cycles or leading to cycles are unsafe.

2. Choose an approach

Decide between DFS with cycle detection and memoization, or reverse graph with topological sort. Explain the trade-offs: DFS is simpler to code, reverse graph is iterative and avoids recursion depth issues.

3. Implement the algorithm

For DFS: use three states (unvisited, visiting, safe) to detect cycles and mark safe nodes. For reverse graph: build reverse adjacency, compute out-degrees, and use a queue to process nodes with out-degree 0, marking them safe and decrementing out-degrees of predecessors.

4. Collect and sort results

After processing, gather all safe nodes and sort them in ascending order as required. Return the sorted list.

5. Analyze complexity and test

State time and space complexity: O(V+E) time, O(V+E) space. Walk through a small example to verify correctness, including a cycle and a terminal node.

Key Points to Mention

  • Definition of safe node: all paths lead to terminal node.
  • Cycle detection is crucial; nodes in cycles are unsafe.
  • Use of reverse graph and topological sort (Kahn's algorithm) for iterative solution.
  • DFS with memoization and three-color marking (white, gray, black) for recursive solution.
  • Time and space complexity: O(V+E) for both approaches.
  • Edge cases: empty graph, single node, self-loops, disconnected components.

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