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 12 coding interview problems | Uber Coding Question

Quick Overview

This multi-problem set evaluates broad algorithmic problem-solving skills, including bitwise reasoning, sliding-window and frequency analysis, stack/monotonic patterns, graph/DP reasoning with constrained jumps, and tree-path parity techniques.

Solve 12 coding interview problems

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Below are multiple independent coding problems. --- ## Problem 1: Reduce an integer to 0 with \(\pm 2^i\) You are given a positive integer \(n\). In one operation you may replace \(n\) with \(n + 2^i\) or \(n - 2^i\) for any integer \(i \ge 0\). **Task:** Return the minimum number of operations needed to make \(n = 0\). **Constraints (typical):** \(1 \le n \le 10^{18}\). --- ## Problem 2: Shortest subarray with at least \(k\) distinct integers You are given an integer array `arr` of length \(n\) and an integer \(k\). A subarray is **good** if it contains **at least \(k\)** distinct values. **Task:** Return the length of the shortest good subarray. If no such subarray exists, return `-1`. **Constraints (typical):** \(1 \le n \le 2\times 10^5\). --- ## Problem 3: Apply the first valid discount to the right You are given an array `prices`. For each index `i`, define the discount as the first index `j > i` such that `prices[j] <= prices[i]`. - If such `j` exists: `final[i] = prices[i] - prices[j]` - Otherwise: `final[i] = prices[i]` (sold at full price) **Task:** Output: 1. The **sum** of all final prices. 2. The list of **0-based indices** that are sold at full price, in increasing order. **Constraints (typical):** \(1 \le n \le 2\times 10^5\). --- ## Problem 4: Max-score jump game with special prime jumps You are given an integer array `arr` of length \(n\). You start at index `0` and must end at index `n-1`. From index `i`, you may jump to: - `i + 1`, or - `i + p` where `p` is a **prime number** and `p % 10 == 3` (e.g., 3, 13, 23, 43, ...), and `i + p < n`. Your score is the sum of `arr` values on all visited indices (including start and end). **Task:** Return the maximum achievable score when reaching `n-1`. If `n-1` is unreachable, return `-1`. **Constraints (typical):** \(1 \le n \le 2\times 10^5\), `arr[i]` may be negative. --- ## Problem 5: Count ancestor endpoints whose path can be permuted into a palindrome You are given a rooted tree with nodes `0..n-1` (root is node `0`). Each node has a lowercase letter. Input is provided as: - `treeNodes = n` - `nodes`: a char array of length `n`, where `nodes[i]` is the character on node `i` - `nodeFrom`, `nodeTo`: arrays of length `n-1` describing directed parent→child edges (`nodeFrom[i] -> nodeTo[i]`), forming a tree - `queries`: array of start nodes For each query start node `u`: - Consider all endpoints `v` on the path from `u` up to the root `0` (i.e., `v` can be `u`, its parent, ..., `0`). - Let the multiset of characters on the path `u -> ... -> v` (inclusive) be collected. - This path is counted if its characters can be **rearranged** into a palindrome (i.e., at most one character has an odd frequency). **Task:** For each query `u`, return how many such endpoints `v` exist. **Constraints (typical):** \(n, q \le 2\times 10^5\). --- ## Problem 6: Maximize pipeline throughput under a scaling budget You have \(n\) services connected in a pipeline. The pipeline throughput is: \[ T = \min_i throughput[i] \] You may scale service `i` any number of times. Each scaling: - increases `throughput[i]` by `1` - costs `scale_cost[i]` Given integer `budget`, **total scaling cost** must be \(\le budget\). **Task:** Return the maximum achievable pipeline throughput `T`. **Constraints (typical):** \(n \le 2\times 10^5\), values up to \(10^{18}\). --- ## Problem 7: Elevator-then-stairs with energy-dependent stair time You must go from floor `0` to floor `N`. You may take the elevator first from floor `0` to floor `x` (choose `x` once, `0 <= x <= N`). - For each elevator floor ascended: gain `e1` energy and spend `t1` time. - After elevator: your energy is `E = x * e1`. Then you must climb the remaining `N - x` floors using stairs. For each stair floor: - At the **start** of the floor, if current energy is `E`, the time spent is `ceil(c / E)`. - Then you spend `e2` energy: `E := E - e2`. - Energy may never become negative; if `E < 0` at any step, that choice of `x` is invalid. **Task:** Choose `x` to minimize total time. If no `x` is feasible, return `-1`. **Constraints (typical):** \(1 \le N \le 10^6\), parameters are positive integers. --- ## Problem 8: Assign tasks to two people with exactly \(k\) tasks for person A You have `n` tasks. If task `i` is done by: - person A: reward `reward1[i]` - person B: reward `reward2[i]` Each task must be assigned to exactly one person. Person A must do **exactly `k` tasks**. **Task:** Return the maximum possible total reward. **Constraints (typical):** \(n \le 2000\), \(0 \le k \le n\). --- ## Problem 9: Score from each start index with energy thresholds You are given: - `layers[0..n-1]`: energy cost to attempt/pass level `j` - `energyReq[0..n-1]`: minimum remaining energy needed *after paying the cost* to pass level `j` - initial energy `K` Starting from index `i`: - Set `E = K`. - For `j = i..n-1`: 1. Pay the level cost: `E := E - layers[j]`. If `E < 0`, stop. 2. If `E >= energyReq[j]`, you pass and gain 1 point; otherwise stop (cannot proceed further). **Task:** Return an array `score` of length `n` where `score[i]` is the number of points you can earn starting at level `i`. **Note:** An \(O(n^2)\) solution will time out; design a faster approach. --- ## Problem 10: Buy the maximum number of consecutive items per query You are given `prices[0..n-1]` (positive integers). Each query provides: - `pos` (1-based starting index) - `amount` (budget) From index `start = pos - 1`, you can buy items consecutively to the right while the running sum does not exceed `amount`. **Task:** For each query, return the maximum number of items you can buy. **Constraints (typical):** \(n, q \le 2\times 10^5\). --- ## Problem 11: Minimum edge reversals so every node can reach the chosen root You are given `n` nodes and `n-1` directed edges `edges[i] = [a, b]` meaning `a -> b`. Ignoring direction, the graph is a tree. For each node `r` considered as the root, you may reverse any subset of edges. **Task:** Compute `res[r]` = the minimum number of edge reversals required so that **every node has a directed path to `r`** (equivalently, all edges point toward `r` along the tree). Return `res` for all `r`. **Constraints (typical):** \(n \le 2\times 10^5\). --- ## Problem 12: For each \(w\), do values \(1..w\) occupy a contiguous block? You are given a permutation `perm[0..n-1]` containing each integer from `1` to `n` exactly once. For each window size \(w = 1..n\), define `ans[w] = 1` if the positions of the numbers `{1,2,...,w}` in `perm` form a contiguous subarray (in any order). Otherwise, `ans[w] = 0`. Equivalently, let `pos[x]` be the index where value `x` appears. Then `ans[w] = 1` iff: \[ \max_{1\le x\le w} pos[x] - \min_{1\le x\le w} pos[x] + 1 = w. \] **Task:** Return `ans[1..n]`. **Constraints (typical):** \(n \le 2\times 10^5\).

Loading coding console...

Part 1: Reduce an Integer to 0 with +/- Powers of Two

You are given a non-negative integer n. In one operation, you may replace n with n + 2^i or n - 2^i for any integer i >= 0. Return the minimum number of operations needed to make n equal to 0.

Constraints

0 <= n <= 10^18

Examples

Input: (0,)

Expected Output: 0

Explanation: Already at 0, so no operations are needed.

Input: (1,)

Expected Output: 1

Explanation: Use -1 once.

Input: (3,)

Expected Output: 2

Explanation: One optimal sequence is 3 -> 4 -> 0.

Input: (39,)

Expected Output: 3

Explanation: For example: 39 -> 40 -> 32 -> 0.

Solution

def solution(n):
    from functools import lru_cache
    n = abs(n)

    @lru_cache(None)
    def dp(x):
        if x == 0:
            return 0
        if x == 1:
            return 1
        if x % 2 == 0:
            return dp(x // 2)
        return 1 + min(dp((x - 1) // 2), dp((x + 1) // 2))

    return dp(n)

Time complexity: O(log n). Space complexity: O(log n).

Hints

If n is even, think about factoring out a power of 2.
If n is odd, your first move must make it even: compare n - 1 and n + 1.

Part 2: Shortest Subarray with At Least k Distinct Integers

Given an integer array arr and an integer k, find the length of the shortest contiguous subarray that contains at least k distinct values. If no such subarray exists, return -1.

Constraints

0 <= len(arr) <= 2 * 10^5
1 <= k <= 2 * 10^5

Examples

Input: ([], 1)

Expected Output: -1

Explanation: There is no subarray at all.

Input: ([1], 1)

Expected Output: 1

Explanation: The single element subarray already has 1 distinct value.

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

Expected Output: 3

Explanation: One shortest good subarray is [2, 1, 3].

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

Expected Output: -1

Explanation: The array contains only one distinct value.

Solution

def solution(arr, k):
    if k <= 0:
        return 0
    n = len(arr)
    freq = {}
    distinct = 0
    left = 0
    best = n + 1

    for right, value in enumerate(arr):
        if freq.get(value, 0) == 0:
            distinct += 1
        freq[value] = freq.get(value, 0) + 1

        while distinct >= k:
            best = min(best, right - left + 1)
            out = arr[left]
            freq[out] -= 1
            if freq[out] == 0:
                del freq[out]
                distinct -= 1
            left += 1

    return -1 if best == n + 1 else best

Time complexity: O(n). Space complexity: O(min(n, number of distinct values)).

Hints

A sliding window can track how many distinct values are inside the current range.
Once a window has at least k distinct numbers, try shrinking it from the left.

Part 3: Apply the First Valid Discount to the Right

For each price at index i, find the first index j > i such that prices[j] <= prices[i]. If such j exists, the final price is prices[i] - prices[j]; otherwise, the item is sold at full price. Return both the sum of all final prices and the list of 0-based indices sold at full price.

Constraints

0 <= len(prices) <= 2 * 10^5
1 <= prices[i] <= 10^9

Examples

Input: ([],)

Expected Output: (0, [])

Explanation: No items means total 0 and no full-price indices.

Input: ([8, 4, 6, 2, 3],)

Expected Output: (15, [3, 4])

Explanation: Final prices are [4, 2, 4, 2, 3].

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

Expected Output: (10, [0, 1, 2, 3])

Explanation: No item gets a discount.

Input: ([10, 1, 1, 6],)

Expected Output: (16, [2, 3])

Explanation: Final prices are [9, 0, 1, 6].

Solution

def solution(prices):
    n = len(prices)
    final_sum = sum(prices)
    stack = []
    discounted = [False] * n

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            idx = stack.pop()
            final_sum -= price
            discounted[idx] = True
        stack.append(i)

    full_price_indices = [i for i, used_discount in enumerate(discounted) if not used_discount]
    return final_sum, full_price_indices

Time complexity: O(n). Space complexity: O(n).

Hints

The phrase first smaller-or-equal value to the right suggests a monotonic stack.
When a new price resolves discounts for earlier items, update the total immediately.

Part 4: Max-Score Jump Game with Special Prime Jumps

You are given an integer array arr. Start at index 0 and reach index n - 1. From index i, you may jump to i + 1, or to i + p where p is a prime number ending in digit 3 and i + p < n. Your score is the sum of arr values at all visited indices, including the start and end. Return the maximum achievable score. In this version, n is small enough for dynamic programming over all valid jump lengths.

Constraints

0 <= len(arr) <= 5000
-10^9 <= arr[i] <= 10^9

Examples

Input: ([],)

Expected Output: -1

Explanation: There is no start or end index.

Input: ([7],)

Expected Output: 7

Explanation: Start and end are the same index.

Input: ([5, -100, 4, 10],)

Expected Output: 15

Explanation: Jump directly from index 0 to index 3 using length 3.

Input: ([5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20],)

Expected Output: 25

Explanation: A jump of length 13 skips all the negative values.

Solution

def solution(arr):
    n = len(arr)
    if n == 0:
        return -1
    if n == 1:
        return arr[0]

    limit = n - 1
    sieve = [True] * (limit + 1)
    if limit >= 0:
        sieve[0] = False
    if limit >= 1:
        sieve[1] = False
    i = 2
    while i * i <= limit:
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
        i += 1

    special_primes = [p for p in range(3, limit + 1) if sieve[p] and p % 10 == 3]

    dp = [0] * n
    dp[0] = arr[0]
    for i in range(1, n):
        best_prev = dp[i - 1]
        for p in special_primes:
            if p > i:
                break
            if dp[i - p] > best_prev:
                best_prev = dp[i - p]
        dp[i] = best_prev + arr[i]

    return dp[-1]

Time complexity: O(n * p), where p is the number of allowed prime jump lengths less than n. Space complexity: O(n + p).

Hints

Precompute all allowed jump lengths less than n with a sieve.
Let dp[i] be the best score for reaching index i.

Part 5: Count Ancestor Endpoints Whose Path Can Be Rearranged into a Palindrome

You are given a rooted tree with root 0. Each node has a lowercase letter. For each query node u, count how many ancestor endpoints v on the path from u up to 0 make the path u -> ... -> v have character counts that can be rearranged into a palindrome.

Constraints

1 <= treeNodes <= 2 * 10^5
1 <= len(queries) <= 2 * 10^5
nodes[i] is a lowercase English letter

Examples

Input: (5, ['a', 'b', 'a', 'c', 'b'], [0, 0, 1, 1], [1, 2, 3, 4], [4, 3, 2, 0])

Expected Output: [3, 1, 2, 1]

Explanation: For node 4, all three ancestor endpoints 4, 1, and 0 are valid.

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

Expected Output: [3, 2]

Explanation: On the chain, node 3 has three valid ancestor endpoints.

Input: (1, ['z'], [], [], [0])

Expected Output: [1]

Explanation: The only path is the single node itself.

Solution

def solution(treeNodes, nodes, nodeFrom, nodeTo, queries):
    n = treeNodes
    if n == 0:
        return [0] * len(queries)

    children = [[] for _ in range(n)]
    for a, b in zip(nodeFrom, nodeTo):
        children[a].append(b)

    bits = [1 << (ord(ch) - 97) for ch in nodes]
    answers = [0] * n

    from collections import defaultdict
    freq = defaultdict(int)
    freq[0] = 1

    stack = [(0, 0, 0)]
    while stack:
        u, mask, state = stack.pop()
        if state == 0:
            current = mask ^ bits[u]
            total = freq.get(current, 0)
            for b in range(26):
                total += freq.get(current ^ (1 << b), 0)
            answers[u] = total

            freq[current] += 1
            stack.append((u, current, 1))
            for v in reversed(children[u]):
                stack.append((v, current, 0))
        else:
            freq[mask] -= 1
            if freq[mask] == 0:
                del freq[mask]

    return [answers[u] for u in queries]

Time complexity: O(26 * n + q). Space complexity: O(n).

Hints

A multiset can be rearranged into a palindrome iff at most one character has odd frequency.
Track parity with a 26-bit mask and count ancestor-prefix masks along the current DFS path.

Part 6: Maximize Pipeline Throughput Under a Scaling Budget

A pipeline has n services, and the overall throughput is the minimum value in the throughput array. You may increase throughput[i] by 1 any number of times, and each unit increase costs scale_cost[i]. Given a total budget, return the maximum achievable pipeline throughput.

Constraints

1 <= len(throughput) <= 2 * 10^5
1 <= throughput[i], scale_cost[i], budget <= 10^18

Examples

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

Expected Output: 4

Explanation: Raising the 2 up to 4 costs 2, but reaching 5 would cost too much.

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

Expected Output: 2

Explanation: All three services can be raised from 1 to 2 exactly within budget.

Input: ([5], [10], 100)

Expected Output: 15

Explanation: A single service can be raised by 10.

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

Expected Output: 3

Explanation: With zero budget, the current minimum stays unchanged.

Solution

def solution(throughput, scale_cost, budget):
    if not throughput:
        return 0

    low = min(throughput)
    high = max(throughput) + budget // min(scale_cost) + 1

    def can(target):
        total = 0
        for t, c in zip(throughput, scale_cost):
            if t < target:
                total += (target - t) * c
                if total > budget:
                    return False
        return True

    while low + 1 < high:
        mid = (low + high) // 2
        if can(mid):
            low = mid
        else:
            high = mid

    return low

Time complexity: O(n log M), where M is the answer range. Space complexity: O(1).

Hints

If you can achieve throughput T, then every smaller target is also achievable.
Binary search the answer and write a function that computes the cost of reaching a target minimum.

Part 7: Elevator-Then-Stairs with Energy-Dependent Stair Time

You must go from floor 0 to floor N. First, choose a single elevator ride from floor 0 to floor x. Each elevator floor gives e1 energy and costs t1 time. Then climb the remaining floors by stairs. For each stair floor, if your current energy is E, the time spent is ceil(c / E), then your energy decreases by e2. Choose x to minimize total time. In this version, N is small enough to try every split.

Constraints

0 <= N <= 4000
1 <= e1, t1, e2, c <= 10^9

Examples

Input: (0, 5, 2, 3, 10)

Expected Output: 0

Explanation: No movement is required.

Input: (3, 5, 2, 2, 10)

Expected Output: 5

Explanation: Best choice is x = 2, giving total time 4 + 1 = 5.

Input: (4, 1, 5, 1, 3)

Expected Output: 15

Explanation: Best choice is x = 2.

Input: (1, 1, 10, 5, 5)

Expected Output: 10

Explanation: Going fully by elevator is the only feasible option.

Solution

def solution(N, e1, t1, e2, c):
    if N == 0:
        return 0

    best = float('inf')

    for x in range(N + 1):
        stairs = N - x
        energy = x * e1

        if energy < stairs * e2:
            continue

        total_time = x * t1
        feasible = True

        for _ in range(stairs):
            if energy <= 0:
                feasible = False
                break
            total_time += (c + energy - 1) // energy
            energy -= e2
            if energy < 0:
                feasible = False
                break

        if feasible and total_time < best:
            best = total_time

    return -1 if best == float('inf') else best

Time complexity: O(N^2). Space complexity: O(1).

Hints

Try every possible elevator stop x from 0 to N.
A choice is feasible only if the starting elevator energy is enough to pay for all remaining stair floors.

Part 8: Assign Tasks to Two People with Exactly k Tasks for Person A

There are n tasks. If task i is assigned to person A, you earn reward1[i]. If assigned to person B, you earn reward2[i]. Every task must be assigned to exactly one person, and person A must receive exactly k tasks. Return the maximum total reward.

Constraints

1 <= len(reward1) == len(reward2) <= 2000
0 <= k <= n
0 <= reward1[i], reward2[i] <= 10^9

Examples

Input: ([8, 7, 15], [5, 10, 5], 2)

Expected Output: 33

Explanation: Choose tasks 0 and 2 for person A.

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

Expected Output: 15

Explanation: All tasks go to person B.

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

Expected Output: 6

Explanation: All tasks must go to person A.

Input: ([10], [1], 1)

Expected Output: 10

Explanation: The single task goes to person A.

Solution

def solution(reward1, reward2, k):
    base = sum(reward2)
    deltas = sorted((a - b for a, b in zip(reward1, reward2)), reverse=True)
    return base + sum(deltas[:k])

Time complexity: O(n log n). Space complexity: O(n).

Hints

Start by assigning every task to person B.
Switching task i from B to A changes the total by reward1[i] - reward2[i].

Part 9: Score from Each Start Index with Energy Thresholds

You are given arrays layers and energyReq, and an initial energy K. Starting from index i, you process levels from i to the end. For each level j, first subtract layers[j] from energy. If energy becomes negative, you stop. Otherwise, if the remaining energy is at least energyReq[j], you gain 1 point and continue; if not, you stop. Return score[i] for every start index i.

Constraints

0 <= len(layers) == len(energyReq) <= 2 * 10^5
0 <= layers[i], energyReq[i], K <= 10^18

Examples

Input: ([], [], 10)

Expected Output: []

Explanation: No levels means no scores.

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

Expected Output: [1, 2, 1]

Explanation: Starting at index 1 lets you pass levels 1 and 2.

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

Expected Output: [0, 1]

Explanation: Starting at 0 fails immediately because the cost is too high.

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

Expected Output: [3, 3, 2, 1]

Explanation: The first failure from index 0 happens only at the last level.

Solution

def solution(layers, energyReq, K):
    n = len(layers)
    if n == 0:
        return []

    pref = [0] * (n + 1)
    for i, x in enumerate(layers):
        pref[i + 1] = pref[i] + x

    need = [pref[i + 1] + max(0, energyReq[i]) - K for i in range(n)]

    size = 1
    while size < n:
        size *= 2

    seg = [float('-inf')] * (2 * size)
    for i, v in enumerate(need):
        seg[size + i] = v
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2 * i], seg[2 * i + 1])

    def first_greater(node, nl, nr, left, threshold):
        if nr <= left or seg[node] <= threshold:
            return n
        if nr - nl == 1:
            return nl
        mid = (nl + nr) // 2
        res = first_greater(node * 2, nl, mid, left, threshold)
        if res != n:
            return res
        return first_greater(node * 2 + 1, mid, nr, left, threshold)

    ans = [0] * n
    for i in range(n):
        j = first_greater(1, 0, size, i, pref[i])
        ans[i] = (n - i) if j == n else (j - i)

    return ans

Time complexity: O(n log n). Space complexity: O(n).

Hints

Rewrite the pass condition using prefix sums.
For each i, you need the first j >= i where a precomputed threshold exceeds prefix[i].

Part 10: Buy the Maximum Number of Consecutive Items per Query

You are given positive prices and multiple queries. Each query gives a 1-based starting position pos and a budget amount. Starting from pos, buy consecutive items to the right while the running total does not exceed the budget. Return the maximum number of items that can be bought for each query.

Constraints

0 <= len(prices), len(queries) <= 2 * 10^5
1 <= prices[i], amount <= 10^18

Examples

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

Expected Output: [2, 3, 1]

Explanation: From position 2 with budget 6, you can buy 1 + 3 + 2.

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

Expected Output: [0, 1]

Explanation: The first budget is too small; the second buys exactly one item.

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

Expected Output: [0, 1, 3]

Explanation: The full budget 9 buys all three items from the start.

Solution

def solution(prices, queries):
    from bisect import bisect_right

    pref = [0]
    for p in prices:
        pref.append(pref[-1] + p)

    ans = []
    for pos, amount in queries:
        start = pos - 1
        target = pref[start] + amount
        right = bisect_right(pref, target) - 1
        ans.append(right - start)

    return ans

Time complexity: O((n + q) log n). Space complexity: O(n).

Hints

Because prices are positive, prefix sums are strictly increasing.
For each query, use binary search on the prefix sum array.

Part 11: Minimum Edge Reversals so Every Node Can Reach the Chosen Root

You are given n nodes and n - 1 directed edges that form a tree if directions are ignored. For every possible root r, compute the minimum number of edge reversals needed so that every node has a directed path to r.

Constraints

1 <= n <= 2 * 10^5
len(edges) == n - 1

Examples

Input: (1, [])

Expected Output: [0]

Explanation: A single node needs no reversals.

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

Expected Output: [1, 0, 1]

Explanation: Root 1 already has all edges effectively pointing toward it.

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

Expected Output: [3, 2, 2, 2]

Explanation: With root 0, all three edges must be reversed.

Solution

def solution(n, edges):
    if n == 0:
        return []

    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append((b, 1))
        adj[b].append((a, 0))

    res = [0] * n
    parent = [-1] * n
    order = []
    stack = [0]

    while stack:
        u = stack.pop()
        order.append(u)
        for v, w in adj[u]:
            if v == parent[u]:
                continue
            parent[v] = u
            res[0] += w
            stack.append(v)

    for u in order:
        for v, w in adj[u]:
            if v == parent[u]:
                continue
            res[v] = res[u] + (1 if w == 0 else -1)

    return res

Time complexity: O(n). Space complexity: O(n).

Hints

First compute the answer for one root, such as 0.
When rerooting across an edge, the answer changes by exactly 1 in one direction or the other.

Part 12: For Each w, Do Values 1..w Occupy a Contiguous Block?

You are given a permutation perm of the integers 1 through n. For every w from 1 to n, determine whether the positions of the values 1, 2, ..., w form a contiguous subarray in perm. Return an array of 0/1 answers.

Constraints

0 <= len(perm) <= 2 * 10^5
perm is a permutation of 1..n

Examples

Input: ([],)

Expected Output: []

Explanation: No values means no answers.

Input: ([1],)

Expected Output: [1]

Explanation: The set {1} always forms a contiguous block.

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

Expected Output: [1, 0, 1, 1]

Explanation: For w = 3, the positions of 1, 2, and 3 span exactly length 3.

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

Expected Output: [1, 1, 0, 1, 1]

Explanation: Values 1 and 2 are adjacent, but values 1..3 are not in one block.

Solution

def solution(perm):
    n = len(perm)
    if n == 0:
        return []

    pos = [0] * (n + 1)
    for i, value in enumerate(perm):
        pos[value] = i

    ans = []
    lo = n
    hi = -1
    for w in range(1, n + 1):
        p = pos[w]
        if p < lo:
            lo = p
        if p > hi:
            hi = p
        ans.append(1 if hi - lo + 1 == w else 0)

    return ans

Time complexity: O(n). Space complexity: O(n).

Hints

Store the position of each value.
As w grows from 1 to n, update only the current minimum and maximum position.