← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Uber SWE interview with a graph problem that looks manageable until you realize the rerooting trick is what they're actually testing for.

Questions Asked (1)

Q1

Given a directed graph that forms a tree when treated as undirected, find the minimum number of edges that need to be reversed so every node can reach node 0.

Algorithms & Data Structures
Author's notes

My first instinct was just BFS from 0 and count wrong-direction edges.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a tree rooted at node 0 and use DFS/BFS to traverse from node 0. For each edge, if it points away from node 0 (parent to child), it must be reversed; if it points toward node 0 (child to parent), it's already correct. Count the number of edges that need reversal.

Pro tip: Clarify that the graph is a tree when undirected, so there are no cycles and exactly n-1 edges. This simplifies the problem to a single traversal, and you can solve it in O(n) time.

1. Understand the problem

Restate the problem: Given a directed graph that is a tree when undirected, we need to reverse the minimum number of edges so that every node can reach node 0. This means all edges must be directed toward node 0.

2. Choose traversal method

Use DFS or BFS starting from node 0 to traverse the tree. Since the graph is a tree, we can treat it as undirected for traversal, but we must consider the original direction of each edge.

3. Count reversals during traversal

During traversal, for each edge from current node u to neighbor v, if the original edge is directed from u to v (i.e., away from node 0), it needs to be reversed. If it's directed from v to u (toward node 0), it's already correct. Increment a counter for each reversal needed.

4. Return the count

After traversing all nodes, the counter holds the minimum number of edges to reverse. Return this count as the answer.

Key Points to Mention

  • The graph is a tree when undirected, so it has exactly n-1 edges and no cycles.
  • Root the tree at node 0 and consider the direction of edges relative to the root.
  • An edge directed away from node 0 (parent to child) must be reversed; an edge directed toward node 0 (child to parent) is already correct.
  • Use DFS or BFS to traverse the tree in O(n) time and O(n) space.
  • The problem reduces to counting edges that are not oriented toward node 0.
  • Edge cases: single node (0 reversals), star graph, path graph.

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