How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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

Q: Find minimum reversals to orient edges away from root

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.

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.

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.

Find minimum reversals to orient edges away from root

Quick Overview

Input

Output

Example

Constraints (typical)

Comments (0)

Find minimum reversals to orient edges away from root

Quick Overview

Input

Output

Example

Constraints (typical)

Comments (0)