Top-Down Employee Reporting Forest
Okta● MediumFULLTIMEONSITE INTERVIEWProblem statement
Each row of employeeManager is [employee, manager]. An empty manager string marks a root. The rows describe a valid reporting forest: every employee appears once, every non-empty manager is also an employee, and there are no cycles.
Return the forest in deterministic top-down preorder. Visit roots in lexicographic order and visit each manager's direct reports in lexicographic order. Encode each visited employee as depth:name, where roots have depth 0.
Function
topDownReportingForest(employeeManager: String[][]) → String[]Examples
Example 1
employeeManager = [["alice",""],["bob","alice"],["cara","alice"],["dan","bob"]]return = ["0:alice","1:bob","2:dan","1:cara"]A preorder walk visits Alice, Bob's subtree, and then Cara.
Example 2
employeeManager = [["zane",""],["amy",""],["lee","zane"]]return = ["0:amy","0:zane","1:lee"]The two roots are ordered lexicographically before their subtrees are traversed.
Example 3
employeeManager = [["solo",""]]return = ["0:solo"]A one-person organization is a one-node forest.
Constraints
1 <= employeeManager.length <= 100000.- Every row has exactly two strings.
- Employee names are unique non-empty lowercase identifiers.
- The manager is either empty or names another employee.
- The relationships form a forest.