FastPrepHubs With the Shortest Longest Chain
Problems/Hubs With the Shortest Longest Chain

Hubs With the Shortest Longest Chain

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Given a tree of departments, this problem returns the departments in its middle: those whose farthest department is the fewest links away. An Adobe MTS-2 report gives the task for its first round in a long written-out form with two small examples; it lets the answer come in any order and states no limits.

Our choices: the answer is sorted in increasing order so it can be judged exactly, at most 2000 departments, and new examples (the report's are not reused).

The judged task matches the report at about 90%.

A company has n departments, numbered 0 to n - 1. Each pair in edges is a direct reporting line between two departments, and together the lines form a tree.

If department h is chosen as the central hub, its longest chain is the largest number of reporting lines between h and any other department.

Return every department whose longest chain is as small as possible, in increasing order.

Function

findHubs(n: int, edges: int[][]) → int[]

Examples

Example 1

n = 6edges = [[0,1],[1,2],[2,3],[2,4],[4,5]]return = [2]

Department 2 is at most 2 reporting lines from everyone (2 → 1 → 0 and 2 → 4 → 5). Every other department has a chain of 3 or more to its farthest department, so the answer is [2].

Example 2

n = 4edges = [[3,2],[2,0],[0,1]]return = [0,2]

The departments form a line 3 - 2 - 0 - 1. Both middle departments, 2 and 0, reach everyone within 2 lines: [0, 2].

Example 3

n = 1edges = []return = [0]

With one department, it is the only hub and its longest chain is 0.

Constraints

  • 1 <= n <= 2000
  • edges.length == n - 1, each edges[i] = [a, b] with 0 <= a, b < n and a != b
  • The edges connect all departments into one tree (no repeated edge and no cycle).

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[] findHubs(int n, int[][] edges) {
    // Write your code here.
}
Checking account…