Inform Employees

Hard
0/120
profile
Contributed by
2 upvotes
Asked in companies
AmazonArcesiumGoogle inc

Problem statement

You are in a company with ‘N’ employees each with a unique ID from ‘0 to N - 1’. You are given a list of managers, where ‘manager[i]’ is the direct manager of ‘ith’ employee. You are also given an array ‘timeToInform’ where ‘timeToInform[i]’ is the time it takes for ‘ith’ employee to send information to all his subordinates. Your task is to find out how much time it will take for any piece of information to reach all employees. You are also given ‘headId’ that is the ID of the head of the company.

For example: 
You are given ‘manager’ = [-1, 0, 0, 1, 1], ‘timeToInform’ = [1, 1, 0, 0, 0], ‘headId’ = [0],

Sample1

We can see employee ‘0’ will take 1 time to inform their subordinates, that are employee 1, and employee 2, and employee 1 will take 1 time to inform their subordinates that are employee 3 and employee 4. The total time taken is 2. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘headId’ representing the number of employees and the employee id of the head of the company.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘manager’ array.

The third line of each test case contains ‘N’ space-separated integers representing the ‘timeToInform’ array.
Output Format: 
For each test case, print a single integer representing the time it takes to inform all the employees

Print a separate line for each test case.
Constraints 
1 <= T <= 10
1 <= N <= 10^5
0 <= headId, manager[i] < N
0 <= timeToInform[i] <= 10^4
manager[headId] = -1

Time Limit = 1 sec
Sample Input 1
2
5 0
-1 0 0 1 1
1 1 0 0 0
3 1
1 -1 0
1 2 0
Sample Output 1:
2
3
Explanation:
For the first test case, ‘manager’ = [-1, 0, 0, 1, 1], ‘timeToInform’ = [1, 1, 0, 0, 0], ‘headId’ = [0],

Sample1

We can see employee ‘0’ will take 1 time to inform their subordinates, that are employee 1, and employee 2, and employee 1 will take 1 time to inform their subordinates that are employee 3 and employee 4. The total time taken is 2. Hence the answer is 2.


For the second test case, ‘manager’ = [1, -1, 0], ‘timeToInform’ = [1, 2, 0], ‘headId’ = 1,

Sample2

We can see employee ‘1’ will take 2 time to inform their subordinates, that is employee ‘0’ and employee ‘0’ will take 1 time to inform their subordinate, i.e, employee 2. Hence the total time taken is 3
Sample Input 2:
2
1 0
-1
0
3 0
-1 0 0
2 0 0
Sample Ouput 2:
0
2
Hint

Try to make a tree out of the given information

Approaches (2)
Depth First Search

In this approach, we can create a tree out of the given information and traverse it. For any node, the time taken is the maximum time taken by its subordinates and the timeToInform of that node.

 

We will create a dfs(employeeId, subordinates, timeToInform), where employeeId is the id of the employee we are currently looking, ‘subordinates’ is the map containing the list of all subordinates of any employee, and ‘timeToInform is the array given in the problem.

 

Algorithm:  

  • In the dfs(employeeId, subordinates, timeToInform)
    • Set maximumTime as 0
    • Iterate sub through subordinates[employeeId]
      • Set maximumTime as maximum of itself and dfs(sub, subordinates, timeToinform) + timeToInform[employeeId]
    • Return maximumTime
  • In the given function
    • Initialise an empty hash map of integers and key and array as values, ‘subordinates’
    • Iterate over all the indices of manager and set m as manager[index]
      • If index is not equal to headId, insert index into subordinates[m]
    • Return dfs(headId, subordinates, timeToInform)
Time Complexity

O(N), Where N is the number of employees in the company

 

We are performing a depth-first search, which, in a tree will cost O(N) time. Hence the final time complexity is O(N).

Space Complexity

O(N), Where N is the number of employees in the company

 

The space complexity of the recursive stack in a depth-first search of a tree is O(N). Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Inform Employees
Full screen
Console