Compute org height and minimal CEO promotions
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
Constraints
- 1 <= n <= 100000
- len(manager) == len(reportee) == n - 1
- Employees are labeled from 1 to n
- Employee 1 is the root (CEO)
- The given relationships form a valid connected tree
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.
Solution
def solution(n, manager, reportee):
if n == 0:
return 0
children = [[] for _ in range(n + 1)]
for m, r in zip(manager, reportee):
children[m].append(r)
level = [0] * (n + 1)
level[1] = 1
order = [1]
ans = 1
i = 0
while i < len(order):
u = order[i]
i += 1
if level[u] > ans:
ans = level[u]
for v in children[u]:
level[v] = level[u] + 1
order.append(v)
return ans
Time complexity: O(n). Space complexity: O(n).
Hints
- Build a children adjacency list from manager -> reportee.
- Run a BFS or DFS from employee 1 while tracking each node's level.
Part 2: Minimum CEO Promotions to Limit Org Height
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.