FastPrepRender an Org Chart and Find Skip-Level Pairs

Render an Org Chart and Find Skip-Level Pairs

Snap Inc. logoSnap Inc.● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

An organization tree is given as relations. Each row contains a manager followed by that manager's direct reports, in display order. Every employee name is unique, every non-root employee has exactly one manager, and the rows describe one valid tree.

Return a two-row result:

  • Row 0 contains the full preorder rendering. The root has no prefix; an employee at depth d is prefixed by exactly 4 * d period characters.
  • Row 1 contains every skip-level pair manager->employee for which the employee is exactly two edges below the manager. Order pairs by the preorder position of the manager and then the preorder position of the employee.

Function

analyzeOrgChart(relations: String[][]) → String[][]

Examples

Example 1

relations = [["A","B","C"],["B","E"],["C","D"]]return = [["A","....B","........E","....C","........D"],["A->E","A->D"]]

E and D are the grandchildren of A.

Example 2

relations = [["M","N"],["N","P"],["P","Q"]]return = [["M","....N","........P","............Q"],["M->P","N->Q"]]

Each length-two ancestor path contributes one pair.

Constraints

  • 1 <= relations.length <= 100000.
  • Each row contains a manager and zero or more direct reports.
  • The total number of employees is at most 100000.
  • Names are nonempty ASCII strings without ->.
  • The input describes one valid rooted tree.

More Snap Inc. problems

See Snap Inc. hiring insights
public String[][] analyzeOrgChart(String[][] relations) {
    // Write your code here.
}
relations[["A","B","C"],["B","E"],["C","D"]]
expected[["A", "....B", "........E", "....C", "........D"], ["A->E", "A->D"]]
Checking account…