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.

Solve Balanced Permutations and Tree Reversals

Quick Overview

This two-part prompt evaluates array and permutation reasoning for detecting contiguous value ranges and directed graph/tree reasoning for minimizing edge reversals when choosing a root, testing competencies in index and interval management, graph traversal and orientation, and algorithmic counting.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You have 90 minutes to solve the following two independent coding problems. ## Problem 1: Balanced Prefix Values in a Permutation You are given a permutation `p` of the integers `1` through `N`. For each `k` from `1` to `N`, consider the positions in `p` of the values `1, 2, ..., k`. Determine whether these `k` elements occupy one contiguous segment of the original array. Return a binary string `ans` of length `N`, where: - `ans[k - 1] = '1'` if the positions of values `1` through `k` are contiguous in `p`. - `ans[k - 1] = '0'` otherwise. ### Example If `p = [4, 1, 3, 2]`: - For `k = 1`, value `{1}` appears contiguously, so output `1`. - For `k = 2`, values `{1, 2}` are at positions `2` and `4`, not contiguous, so output `0`. - For `k = 3`, values `{1, 2, 3}` are at positions `2, 3, 4`, contiguous, so output `1`. - For `k = 4`, all values occupy the whole array, so output `1`. The result is `1011`. ## Problem 2: Minimum Edge Reversals to Root a Directed Tree You are given a directed graph with `N` nodes and `N - 1` directed edges. If edge directions are ignored, the graph forms a tree. You may choose any node as the root. After choosing the root, every edge must point away from the root, meaning every directed edge should go from a parent to a child in the rooted tree. If an edge points in the wrong direction, you may reverse it. Find the minimum possible number of edge reversals over all choices of the root. ### Example Suppose the directed edges are: ```text 1 -> 2 3 -> 2 3 -> 4 ``` If node `3` is chosen as the root, the edges should point away from `3`: ```text 3 -> 2 3 -> 4 2 -> 1 ``` Only edge `1 -> 2` must be reversed, so the answer is `1`.

Quick Answer: This two-part prompt evaluates array and permutation reasoning for detecting contiguous value ranges and directed graph/tree reasoning for minimizing edge reversals when choosing a root, testing competencies in index and interval management, graph traversal and orientation, and algorithmic counting.

Part 1: Balanced Prefix Values in a Permutation

You are given a permutation `p` of the integers `1` through `N`. For every `k` from `1` to `N`, look at the positions of the values `1, 2, ..., k` inside `p`. If those positions form exactly one contiguous segment of the array, then the `k`-th answer bit is `'1'`; otherwise it is `'0'`. Return the full binary string of length `N`.

Constraints

1 <= N <= 2 * 10^5
`p` is a permutation of `1..N`
The solution should run in linear time

Examples

Input: [4, 1, 3, 2]

Expected Output: '1011'

Explanation: Positions of `1,2,3,4` are `2,4,3,1` in 1-based indexing. The sets for `k=1,2,3,4` are contiguous, not contiguous, contiguous, contiguous.

Input: [1, 2, 3, 4]

Expected Output: '1111'

Explanation: Each prefix of values already occupies the first `k` positions.

Input: [2, 1, 4, 3]

Expected Output: '1101'

Explanation: For `k=3`, the values `1,2,3` appear at positions `2,1,4`, which do not form one segment.

Input: [1]

Expected Output: '1'

Explanation: Single-element permutation: the only value is trivially contiguous.

Input: [3, 1, 2, 5, 4]

Expected Output: '11101'

Explanation: Values `1,2,3` occupy positions `2,3,1`, which are contiguous together, but adding `4` breaks contiguity until all five values are included.

Hints

Instead of scanning the permutation for each `k`, first compute where each value appears.
For values `1..k`, they are contiguous exactly when `max_position - min_position + 1 == k`.

Part 2: Minimum Edge Reversals to Root a Directed Tree

You are given `N` nodes and `N - 1` directed edges. If edge directions are ignored, the graph is a tree. You may choose any node as the root. After choosing a root, every edge must point away from the root, from parent to child. You may reverse edges that point the wrong way. Return the minimum number of reversals needed over all possible root choices.

Constraints

1 <= n <= 2 * 10^5
`len(edges) == n - 1`
If directions are ignored, the graph formed by `edges` is a tree
Node labels are integers from `1` to `n`

Examples

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

Expected Output: 1

Explanation: Choosing node `3` as root requires only reversing edge `1 -> 2` into `2 -> 1`.

Input: (1, [])

Expected Output: 0

Explanation: Edge case: a single node has no edges, so no reversals are needed.

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

Expected Output: 0

Explanation: Choosing node `1` as root already makes all edges point away from the root.

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

Expected Output: 0

Explanation: Choosing node `2` as root already gives the correct outward orientation.

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

Expected Output: 2

Explanation: No matter which root is chosen, at least two edges must be reversed. For example, rooting at `2` requires reversing `4 -> 3` and `5 -> 3`.

Hints

First, fix an arbitrary root such as node `1` and count how many edges are wrong for that root.
When you move the root across one edge, the total answer changes by exactly `+1` or `-1` depending on that edge's original direction.

Quick Overview