How should I practice Insert an Employee into an Organization Hierarchy?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Waymo phone screen problems in FastPrep.

Is Insert an Employee into an Organization Hierarchy associated with Waymo?

FastPrep tags this as a Waymo phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Insert an Employee into an Organization Hierarchy

Learn this problem

● Medium

WaymoFULLTIMEPHONE SCREEN

Problem statement

An organization is a rooted tree encoded by strings employeeId|managerId. Exactly one employee is the root and uses manager ID NONE. The order of rows defines the order among siblings.

An employee's score is 1 + number of direct reports. Insert newEmployee into the subtree rooted at requestedManager:

If the requested manager has fewer than k direct reports, attach the new employee there.
Otherwise, search the requested manager's descendants in breadth-first order. Within a level, visit direct reports in their row order.
Attach the new employee to the first visited employee with fewer than k direct reports.

Return the complete updated organization as strings employeeId|managerId|score, sorted by employee ID in ascending lexicographic order.

Function

insertEmployee(organization: String[], requestedManager: String, newEmployee: String, k: int) → String[]

Examples

Example 1

organization = ["ceo|NONE","a|ceo","b|ceo","c|a"]requestedManager = "ceo"newEmployee = "d"k = 2return = ["a|ceo|3","b|ceo|1","c|a|1","ceo|NONE|3","d|a|1"]

ceo already has two direct reports. Breadth-first search visits a before b; a has one open position, so d is attached there. The scores of a and the new employee are 3 and 1.

Example 2

organization = ["root|NONE","east|root","leaf|east"]requestedManager = "root"newEmployee = "rover"k = 1return = ["east|root|2","leaf|east|2","root|NONE|2","rover|leaf|1"]

Both root and east are full. The first available employee in breadth-first order is leaf, so it becomes the new employee's manager.

Constraints

1 <= organization.length <= 200000.
1 <= k <= 100000.
Every employee ID is unique, nonempty, case-sensitive, and contains only English letters, digits, underscores, or hyphens.
newEmployee is not already present, and no employee ID equals NONE.
requestedManager identifies an existing employee.
The input describes one valid rooted tree, and every employee initially has at most k direct reports.