← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Uber SWE interview with a graph problem that looks deceptively simple on the surface. The core challenge was knowing the rerooting DP pattern, which I'd seen before but never had to implement cleanly under pressure.

Questions Asked (1)

Q1

You're given a directed graph on n nodes (labeled 0 to n-1) whose underlying undirected structure is a tree. For each node, find the minimum number of edge reversals required so that every other node is reachable from that node.

Algorithms & Data Structures
Author's notes

I knew this was a tree DP problem pretty fast, but the rerooting part is where I fumbled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding, for each node, the number of edges that must be reversed to make it the root of an arborescence. First compute the answer for an arbitrary root using DFS, then reroot the tree to compute answers for all nodes in O(n) time. The key is to track how the reversal count changes when moving the root from a parent to its child.

Pro tip: Emphasize that the underlying undirected graph is a tree, so there are no cycles and exactly one path between any two nodes. This allows the rerooting technique to work in linear time, which is crucial for large n.

1. Understand the problem and define the metric

Clarify that for a given root, we need to count edges that are directed away from the root (i.e., need reversal to point towards the root). The answer for a node is the number of such edges.

2. Compute answer for an arbitrary root

Pick any node (e.g., 0) as root. Perform a DFS/BFS to compute the number of reversals needed for that root. For each edge, if it points from parent to child, it needs reversal; if from child to parent, it doesn't.

3. Derive rerooting transition

When moving the root from a parent u to a child v, the edge between them changes direction relative to the root. If the original edge was u->v, then for u it needed reversal (counted), but for v it does not; if v->u, then for u it did not, but for v it does. So the new count = old count + (1 if edge is v->u else -1).

4. Perform rerooting DFS to compute all answers

Do a second DFS starting from the initial root, propagating the count to children using the transition. Store the result for each node.

5. Analyze complexity and edge cases

The algorithm runs in O(n) time and O(n) space. Handle n=1 (answer 0) and ensure recursion depth is managed (use iterative DFS if needed).

Key Points to Mention

  • The underlying undirected graph is a tree, so it's connected and acyclic.
  • For a fixed root, the minimum reversals equal the number of edges directed away from the root.
  • Rerooting technique: compute for one root, then adjust for each child in O(1) using the edge direction.
  • Time complexity O(n) and space O(n) are optimal.
  • Use iterative DFS to avoid stack overflow for large n.
  • The problem is equivalent to finding the number of edges that need to be reversed to make the root reach all nodes.

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