DIY: Time Needed to Inform All Employees
Solve the interview question "Time Needed to Inform All Employees" in this lesson.
We'll cover the following
Problem statement
A company has n
employees, and each employee has a unique ID from 0
to n - 1
. The ID of the head of the company is headID
.
Each employee has one direct manager given in the manager
array. In the manager
array, manager[i]
is the direct manager of the i-th
employee, manager[headID] = -1
. Subordinate relationships are also guaranteed to have a tree structure.
The head of the company wants to inform all the company’s employees of an urgent piece of news. The head of the company will inform their direct subordinates, who will inform their subordinates and so on, until all of the employees know the news. Any employee can only relay the message to their immediate subordinates only.
The i-th
employee needs informTime[i]
minutes to inform all of their direct subordinates (After informTime[i]
minutes, all of their direct subordinates can start spreading the news).
Return the number of minutes needed to inform all the employees about the urgent news.
Input
The following is an example input:
n = 6
headID = 2
manager = [2,2,-1,2,2,2]
informTime = [0,0,1,0,0,0]
2
/ / | \ \
0 1 3 4 5
Output
The following is an example output:
1
The company head (with id = 2
) is the only manager of all the employees and needs 1
minute to inform all of them.
Coding exercise
For this coding exercise, you need to implement the num_of_minutes(n, headID, manager, informTime)
function, where n
is the number of employees, headID
represents the company’s head, manager
is the list of managers, and informTime
is the time required by employees to convey the message. The function should return the number of minutes needed to inform all the employees.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.