FastPrepMessage Broadcast Time in an Org Tree
Problems/Message Broadcast Time in an Org Tree

Message Broadcast Time in an Org Tree

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Both parts use a company tree whose root is the CEO. In part one, every manager forwards a message to all direct reports in the same time unit; how long until everyone has it? In part two, a manager forwards to one report per time unit, so a manager who gets the message at time t reaches the reports at t + 1, t + 2 and so on. Both parts came from the first DSA round, and the candidate coded both.

The report gives no input format, limits or examples, and does not say who picks the order in the second part. Here both answers are returned together, the tree is given as a parent array, every manager chooses the order that finishes soonest, and there are at most 800 employees. The examples are our own.

The judged task matches the report at about 85%.

A company has n employees numbered 0 to n - 1. Employee 0 is the CEO, and parent[i] is the manager of employee i (parent[0] = -1).

At time 0 the CEO has a message. A manager can only pass it to their own direct reports, and passing it to one report takes 1 unit of time. Find the earliest time by which every employee has the message, in two settings:

  1. Parallel: a manager tells all of their direct reports at the same moment, 1 unit after they themselves heard it.
  2. One at a time: a manager tells one direct report per unit of time, in any order they choose: the first report hears 1 unit after the manager did, the second 2 units after, and so on. Every manager picks the order that makes the final time as small as possible.

Return [parallelTime, oneAtATimeTime]. With only the CEO, both are 0.

Function

broadcastTimes(parent: int[]) → int[]

Examples

Example 1

parent = [-1,0,0,1,1,1]return = [2,4]

In parallel, employees 1 and 2 hear at time 1 and employees 3, 4 and 5 at time 2, so everyone knows by time 2. One at a time, the CEO should tell employee 1 first (time 1), because employee 1 still has three people to tell; they hear at times 2, 3 and 4. Employee 2 hears from the CEO at time 2. Everyone knows by time 4.

Example 2

parent = [-1]return = [0,0]

The CEO is the only employee, so no message needs to be passed: both times are 0.

Example 3

parent = [-1,0,1]return = [2,2]

A chain: each person has one report, so the order does not matter and both times are 2.

Constraints

  • 1 <= parent.length <= 800
  • parent[0] == -1, and 0 <= parent[i] < parent.length for every i >= 1
  • The reporting lines form one tree with employee 0 at the top (no cycles).

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public int[] broadcastTimes(int[] parent) {
    // Write your code here.
}
Checking account…