← Uber Interview Insights

Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Uber coding interview with a graph problem that looks straightforward until you actually think about it. Reroot DP is the move but I didn't get there cleanly.

Questions Asked (1)

Q1

You're given a directed graph that forms a tree when you ignore edge directions. Find a root node such that the number of edge reversals needed to make all edges point away from it is minimized. Return that minimum count.

Algorithms & Data Structures
Author's notes

I started with brute force, picked an arbitrary root, ran a DFS to count reversals, then tried to re-run for every possible root.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as rerooting on a tree: first root the tree arbitrarily and compute the number of reversals needed for that root using a post-order traversal. Then use a second DFS to compute the answer for all other roots by adjusting the count based on the direction of the edge between parent and child. Finally, return the minimum count over all nodes.

Pro tip: Clarify that the graph is a tree when ignoring directions, so there are no cycles; this allows O(n) rerooting. Also, mention that the minimum reversals equals the minimum number of edges pointing away from the root, which can be computed efficiently.

1. Understand the problem and constraints

Confirm that the graph is a directed tree (underlying undirected graph is a tree) and that we need to find a root minimizing the number of edges that must be reversed to point away from it. Note that n can be large, so an O(n^2) solution is too slow.

2. Root the tree arbitrarily and compute initial reversals

Pick any node (e.g., 0) as the initial root. Perform a DFS/BFS to compute the number of edges that need reversal for this root: count edges directed toward the root (since they need to be reversed to point away).

3. Reroot to compute reversals for all nodes

Use a second DFS to propagate the reversal count from parent to child. When moving the root from u to v, if the edge u->v exists, the count decreases by 1 (since it already points away from v); if v->u exists, the count increases by 1.

4. Find the minimum and return

Track the minimum reversal count across all nodes during the rerooting process. Return that minimum as the answer.

Key Points to Mention

  • Tree property: underlying undirected graph is a tree, so no cycles and exactly n-1 edges.
  • Reversal count for a root equals the number of edges directed toward the root.
  • Rerooting technique: O(n) time by reusing computations from parent to child.
  • Edge direction adjustment: when moving root from u to v, if edge is u->v, count decreases by 1; if v->u, count increases by 1.
  • Time and space complexity: O(n) time and O(n) space for adjacency list and recursion stack.
  • Handling large inputs: iterative DFS to avoid recursion limit if necessary.

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