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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Rippling.

What role is this question designed for?

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

Compute org height and minimal CEO promotions

Quick Overview

This question evaluates understanding of rooted tree data structures, computation of tree height (reporting layers), and algorithmic manipulation of subtrees to minimize maximum depth, testing skills in tree traversal, depth calculation, and constrained optimization.

Compute org height and minimal CEO promotions

Company: Rippling

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an organization chart with **n** employees labeled `1..n`. Employee `1` is the CEO (root). The reporting relationships are given as two integer arrays `manager[]` and `reportee[]` of length `n-1`, where for each index `i`: - `reportee[i]` reports directly to `manager[i]` Assume these pairs form a valid **tree** rooted at the CEO. Define an employee’s **reporting layer** (level) as their distance from the CEO in nodes, with: - `level(1) = 1` (CEO) - each direct report of the CEO has level `2`, etc. ### Task 1. Compute the **maximum reporting layer** in the company (i.e., the tree height in levels): the maximum `level(v)` over all employees `v`. 2. Given an integer threshold `h`, deep reporting chains beyond `h` layers are considered harmful. You may perform the following operation any number of times: - Choose any employee `x != 1` and change their manager so that `x` now **reports directly to the CEO** (i.e., make `manager(x) = 1`). The entire subtree of `x` moves with them. Return the **minimum number of such moves** required so that in the resulting org chart, the maximum reporting layer is **≤ h**. ### Input/Output requirements - **Input:** `n`, arrays `manager[]`, `reportee[]`, and integer `h`. - **Output:** - The original maximum reporting layer (height). - The minimum number of moves to make the final height ≤ `h`. ### Notes / Assumptions - The given relationships form a connected rooted tree with root `1`. - Clarify in your solution whether you treat “height” as number of nodes on the longest root-to-leaf path (levels, as defined above) rather than number of edges.

Quick Answer: This question evaluates understanding of rooted tree data structures, computation of tree height (reporting layers), and algorithmic manipulation of subtrees to minimize maximum depth, testing skills in tree traversal, depth calculation, and constrained optimization.

Part 1: Maximum Reporting Layer in an Org Tree

You are given an organization chart with employees labeled 1..n, where employee 1 is the CEO. The arrays manager and reportee each have length n-1, and reportee[i] reports directly to manager[i]. These relationships form a valid rooted tree. Define reporting layer as the number of nodes on the path from the CEO: level(1) = 1, direct reports of the CEO are at level 2, and so on. Compute the maximum reporting layer in the company. In this problem, height is measured in levels (nodes), not edges.

Constraints

1 <= n <= 100000
len(manager) == len(reportee) == n - 1
Employees are labeled from 1 to n
Employee 1 is the root (CEO)

Loading coding console...

Examples

Input: (1, [], [])

Expected Output:

Explanation: Only the CEO exists, so the maximum layer is 1.

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

Expected Output:

Explanation: This is a chain 1 -> 2 -> 3 -> 4 -> 5, so the deepest level is 5.

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

Expected Output:

Explanation: A balanced tree with CEO at level 1, managers at level 2, and leaves at level 3.

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

Expected Output:

Explanation: The deepest path is 1 -> 2 -> 4 -> 5, which has 4 levels.

Part 2: Minimum CEO Promotions to Limit Org Height

You are given the same organization tree: employees are labeled 1..n, employee 1 is the CEO, and reportee[i] reports directly to manager[i]. The tree is valid and rooted at employee 1. The reporting layer is defined in levels: level(1) = 1, direct reports are level 2, and so on. You are also given an integer h. If the organization has reporting chains deeper than h levels, you may repeatedly perform this operation: choose any employee x != 1 and make x report directly to the CEO. The entire subtree of x moves with them. Return the minimum number of such moves needed so that the final maximum reporting layer is at most h. If this is impossible, return -1. (This only happens when h = 1 and n > 1, because no non-CEO employee can ever be moved to level 1.)

Constraints

1 <= n <= 100000
len(manager) == len(reportee) == n - 1
1 <= h <= n
Employees are labeled from 1 to n
Employee 1 is the root (CEO)
The given relationships form a valid connected tree

Examples

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

Expected Output:

Explanation: A single CEO already has height 1, so no moves are needed.

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

Expected Output:

Explanation: Move employee 4 directly under the CEO. Then the deepest level becomes 3.

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

Expected Output:

Explanation: For the chain of 7 employees, two promotions are required to break it into short enough segments.

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

Expected Output:

Explanation: Promoting employee 3 to report to the CEO makes both employees 4 and 5 end up within 3 levels.

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

Expected Output:

Explanation: With h = 1, only the CEO can be at level 1. Employee 2 can never be moved to level 1.

Solution

def solution(n, manager, reportee, h):
    if n == 0:
        return 0
    if h <= 0:
        return -1
    if h == 1:
        return 0 if n == 1 else -1

    children = [[] for _ in range(n + 1)]
    parent = [0] * (n + 1)
    for m, r in zip(manager, reportee):
        children[m].append(r)
        parent[r] = m

    # level is counted in nodes: CEO is level 1.
    level = [0] * (n + 1)
    level[1] = 1
    order = [1]
    i = 0
    while i < len(order):
        u = order[i]
        i += 1
        for v in children[u]:
            level[v] = level[u] + 1
            order.append(v)

    # Binary lifting for fast ancestor jumps.
    LOG = max(1, n.bit_length())
    up = [[0] * (n + 1) for _ in range(LOG)]
    up[0] = parent[:]
    for j in range(1, LOG):
        prev = up[j - 1]
        cur = up[j]
        for v in range(1, n + 1):
            cur[v] = prev[prev[v]]

    def kth_ancestor(v, k):
        bit = 0
        while k:
            if k & 1:
                v = up[bit][v]
            k >>= 1
            bit += 1
        return v

    # Euler tour on the original tree so we can mark whole subtrees as handled.
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    timer = 0
    stack = [(1, 0)]
    while stack:
        u, state = stack.pop()
        if state == 0:
            timer += 1
            tin[u] = timer
            stack.append((u, 1))
            for v in reversed(children[u]):
                stack.append((v, 0))
        else:
            tout[u] = timer

    # Fenwick tree for range add + point query.
    bit = [0] * (n + 3)

    def add(idx, delta):
        while idx < len(bit):
            bit[idx] += delta
            idx += idx & -idx

    def range_add(left, right, delta):
        add(left, delta)
        add(right + 1, -delta)

    def point_query(idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    # Deepest-first greedy.
    nodes = list(range(1, n + 1))
    nodes.sort(key=lambda x: level[x], reverse=True)

    moves = 0
    jump = h - 2

    for v in nodes:
        if level[v] <= h:
            break
        if point_query(tin[v]) > 0:
            continue
        x = kth_ancestor(v, jump)
        moves += 1
        range_add(tin[x], tout[x], 1)

    return moves

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

Hints

Process employees from deepest to shallowest. If a node is already handled by an earlier move, skip it.
For a node deeper than h, the highest employee you can move while still fixing that node is its ancestor exactly h-2 steps above it.