Report chain headcount
MediumOnline Assessment
Roll up headcounts for a company org chart and flag the people whose reporting chain is broken.
reports is a list of [employee, manager] lines exported from an HR system. A manager of "" (empty) means the employee is at the top of the company. If an employee appears on several lines, only the last line counts (people get reassigned).
Follow an employee's manager, then that manager's manager, and so on. The chain is intact if it ends at someone whose manager is "". It is broken if it reaches a manager who has no line of their own, or if it runs into a loop (including someone who is their own manager). Everybody whose chain passes through a broken person is broken too.
For every intact employee, the headcount is the number of intact employees anywhere below them (direct reports, their reports' reports, and so on), not counting themselves.
Input: reports, a list of [employee, manager] pairs of strings.
Output: a list of two lists. The first holds one string "name headcount" for every intact employee, ordered by headcount descending, then by name ascending (plain character order, so "Zed" comes before "amy"). The second holds the names of all broken employees in ascending order. If the input is empty, return [[], []].
Example 1
- Input:
- [[["ana",""],["bo","ana"],["cy","ana"],["di","bo"],["ed","di"]]]
- Output:
- [["ana 4","bo 2","di 1","cy 0","ed 0"],[]]
- Explanation
- ana has no manager. bo and cy report to ana, di to bo, and ed to di. ana therefore has 4 people below her, bo has 2 (di, ed), di has 1 (ed), and cy and ed have none. Ties are ordered by name: cy before ed.
Example 2
- Input:
- [[["kim",""],["lou","kim"],["max","lou"],["max","kim"],["nat","zed"],["oz","nat"],["pam","pam"]]]
- Output:
- [["kim 2","lou 0","max 0"],["nat","oz","pam"]]
- Explanation
- max appears twice and the last line wins, so max reports to kim. kim has lou and max below, 2 people. nat's manager zed is not in the list, so nat's chain is broken, and so is oz's, who reports to nat. pam reports to pam, a loop, so pam is broken. Broken people are not ranked and not counted.
Example 3
- Input:
- [[["Zed",""],["amy",""],["bob","amy"],["cat","Zed"],["dan","cat"],["eve","bob"],["x","y"],["y","x"],["w","x"]]]
- Output:
- [["Zed 2","amy 2","bob 1","cat 1","dan 0","eve 0"],["w","x","y"]]
- Explanation
- There are two tops. "Zed" has cat and dan below (2); amy has bob and eve (2); the tie is broken by name and uppercase letters sort before lowercase. x and y report to each other and w reports to x, so all three are broken and are listed in ascending order.
Constraints
0 <= reports.length <= 1,200- Each entry is
[employee, manager]; names are 1 to 8 letters or digits and are case-sensitive; a manager of""means top of the company - The reporting chains can be up to 1,000 people deep