How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find minimum reversals to orient edges away from root

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a connected graph with `n` nodes labeled `0..n-1` and `n-1` directed edges. If you ignore edge directions, the edges form a tree. Each directed edge is given as a pair `(u, v)` meaning the edge currently points from `u` to `v`. You are also given a root node `r`. In the rooted tree (rooted at `r`), every edge should point **away from the root** (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs `1`. Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from `r`. #### Input - Integer `n` - List of directed edges `edges`, length `n-1`, each as `(u, v)` - Integer root `r` #### Output - Integer: minimum number of reversals #### Example Suppose `n = 5`, `r = 0`, and edges are: - `(1, 0)`, `(0, 2)`, `(3, 2)`, `(3, 4)` Ignoring directions, the tree is `0-1`, `0-2`, `2-3`, `3-4`. To make all edges point away from `0`, edges `(1,0)` and `(3,2)` must be reversed, so the answer is `2`. #### Constraints (typical) - `1 <= n <= 2e5` - The undirected version of `edges` is a tree - Nodes are `0..n-1` *Note:* With large `n`, recursive DFS may overflow the call stack in some languages; an iterative traversal may be required.

Quick Answer: This question evaluates understanding of directed graphs and rooted trees, the ability to reason about edge orientations and minimal reversals, and competency in traversal techniques and complexity analysis.

You are given a connected graph with `n` nodes labeled `0..n-1` and `n-1` directed edges. If you ignore edge directions, the edges form a tree. Each directed edge is given as a pair `(u, v)` meaning the edge currently points from `u` to `v`. You are also given a root node `r`. In the rooted tree (rooted at `r`), every edge should point **away from the root** (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs `1`. Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from `r`. #### Input - Integer `n` - List of directed edges `edges`, length `n-1`, each as `(u, v)` - Integer root `r` #### Output - Integer: minimum number of reversals #### Example Suppose `n = 5`, `r = 0`, and edges are `(1, 0)`, `(0, 2)`, `(3, 2)`, `(3, 4)`. Ignoring directions, the tree is `0-1`, `0-2`, `2-3`, `3-4`. To make all edges point away from `0`, edges `(1,0)` and `(3,2)` must be reversed, so the answer is `2`. *Note:* With large `n` (up to `2e5`), a single deep path can blow a recursive call stack — use an iterative BFS/DFS traversal.

Constraints

1 <= n <= 2 * 10^5
edges.length == n - 1
The undirected version of edges forms a tree (connected, acyclic)
0 <= u, v, r < n
Each edge is a directed pair (u, v); input orientation may already be correct or reversed

Examples

Input: (5, [(1, 0), (0, 2), (3, 2), (3, 4)], 0)

Expected Output: 2

Explanation: The worked example. Edges (1,0) and (3,2) point toward root 0 along their branches, so both must be reversed.

Input: (1, [], 0)

Expected Output: 0

Explanation: A single node with no edges is already a valid rooted tree; nothing to reverse.

Input: (2, [(0, 1)], 0)

Expected Output: 0

Explanation: Edge (0,1) already points away from root 0 (0 is the parent of 1).

Input: (2, [(0, 1)], 1)

Expected Output: 1

Explanation: Same edge but root is 1, so 1 must be the parent: (0,1) points toward the root and must be reversed.

Input: (4, [(0, 1), (0, 2), (0, 3)], 0)

Expected Output: 0

Explanation: A star already oriented outward from the center root 0 — every edge is correct.

Input: (4, [(1, 0), (2, 0), (3, 0)], 0)

Expected Output: 3

Explanation: All three leaves point inward to root 0; each of the three edges must be reversed.

Input: (6, [(0, 1), (2, 1), (2, 3), (4, 3), (4, 5)], 2)

Expected Output: 2

Explanation: Rooting a path-like tree at the interior node 2. Edges (0,1) and (4,3) end up pointing toward the root along their branches and must be reversed.

Input: (3, [(1, 0), (1, 2)], 1)

Expected Output: 0

Explanation: Root 1 is the parent of both 0 and 2, and both edges already point outward from 1, so no reversals are needed.

Hints

Rooting the tree at r forces a unique target direction for every edge: parent -> child. There is no choice to optimize across edges, so the answer is just the count of edges whose current direction disagrees.
Build an undirected adjacency list so you can walk the tree in any direction, but tag each entry with a cost: for original edge (u, v), add (v, 0) to adj[u] (forward = free) and (u, 1) to adj[v] (backward = one reversal).
Traverse outward from r with BFS or an explicit stack and sum the cost tag of each edge crossed in the parent -> child direction. Use an iterative traversal — a recursive DFS can overflow the stack on a 2e5-deep path.

Quick Overview

This question evaluates understanding of directed graphs and rooted trees, the ability to reason about edge orientations and minimal reversals, and competency in traversal techniques and complexity analysis.