Uber·Software Engineer·Online Assessment (OA)·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Uber SWE online assessment, one graph problem that looks deceptively simple until you realize the naive approach times out on hidden test cases. The whole thing is basically a tree re-rooting DP problem dressed up in edge-reversal clothing.

Questions Asked (2)

Given a directed tree with n nodes and n-1 edges, find the minimum number of edge reversals needed so that every node can reach a chosen root. Either return the minimum over all possible root choices, or return an array of per-root costs depending on the variant.

Algorithms & Data Structures

Author's notes

My first instinct was just re-run a DFS from every node and count reversals each time.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding, for each possible root, the number of edges that need to be reversed so that all nodes can reach the root. Use two DFS passes: first compute the cost for an arbitrary root by counting edges directed away from the root, then reroot the tree to compute costs for all other roots in O(n) total time.

Pro tip: Clarify with the interviewer whether they want the minimum over all roots or the full array of per-root costs, as this changes the output format. Mention that the rerooting technique generalizes to many tree DP problems.

1. Clarify the problem and output format

Confirm whether the function should return the minimum cost over all roots or an array of costs for each root. Also verify that the tree is directed and that reversing an edge means changing its direction.

2. Define the cost for a fixed root

For a given root, the cost is the number of edges that point away from the root (i.e., edges that need to be reversed so they point toward the root). This can be computed by a single DFS from the root.

3. Compute cost for an initial root

Pick an arbitrary root (e.g., node 0) and perform a DFS to count how many edges are directed away from it. This gives the cost for that root.

4. Reroot to compute costs for all nodes

Use a second DFS to propagate the cost from parent to child. When moving the root from u to v, if the edge u->v exists, the cost decreases by 1; if v->u exists, the cost increases by 1. Update the cost for v accordingly.

5. Return the result

If the minimum is required, return the minimum value from the computed costs. If an array is required, return the array of costs for all nodes.

Key Points to Mention

The problem can be solved in O(n) time using two DFS passes (rerooting technique).
For a fixed root, the cost is the number of edges directed away from the root.
When rerooting from u to v, the cost changes by -1 if edge u->v exists, and +1 if edge v->u exists.
The rerooting technique avoids recomputing from scratch for each root, reducing complexity from O(n^2) to O(n).
Edge cases: n=1 (cost 0), and handling large inputs efficiently.
The approach can be extended to return the minimum cost or the full array of costs.

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

A related variant: given n cities connected by n-1 directed roads forming a tree, what is the minimum number of roads to reverse so every city can reach city 0?

Algorithms & Data Structures

Author's notes

This one is actually easier since the root is fixed.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a directed tree rooted at city 0 and perform a DFS/BFS to count edges that point away from the root. The minimum number of reversals equals the number of edges that are directed from a parent to a child (i.e., away from the root).

Pro tip: Clarify that the graph is a tree (n nodes, n-1 edges) and that reversing an edge is the only operation; then emphasize that the answer is simply the count of edges not pointing toward the root. This shows you understand the underlying structure and avoid overcomplicating.

1. Understand the problem

Restate the problem: we have a directed tree rooted at 0, and we need every node to reach 0. Reversing an edge changes its direction. Find the minimum reversals.

2. Choose traversal method

Use DFS or BFS starting from node 0 to traverse the tree, treating edges as undirected for traversal but noting their original direction.

3. Count misdirected edges

During traversal, for each edge from parent u to child v, if the original direction is u→v (away from root), increment a counter; if it's v→u (toward root), do nothing.

4. Return the count

The counter value is the minimum number of edges to reverse. Explain why: each misdirected edge must be reversed at least once, and reversing it fixes the path for all nodes in that subtree.

5. Analyze complexity

Time complexity O(n) because each node and edge is visited once. Space complexity O(n) for recursion stack or queue.

Key Points to Mention

The graph is a tree, so there is exactly one path between any two nodes.
Root the tree at city 0 to define parent-child relationships.
An edge directed away from the root (parent→child) must be reversed; an edge toward the root (child→parent) is already correct.
The minimum number of reversals is exactly the number of edges directed away from the root.
Use DFS/BFS to traverse and count, achieving O(n) time and O(n) space.
Reversing an edge affects only the subtree below it, but since we need all nodes to reach 0, each misdirected edge must be reversed independently.

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