The employee importance problem in Python

In this problem, we’re presented with a workforce management situation. We need to determine how to calculate the importance of an employee within a company. In this Answer, we will explore the problem statement and provide a Python solution for tackling this problem. To do so, we’ll need an understanding of the depth-first search (DFS). Refer to this Answer on DFS for a refresher on the concept.

Problem statement

We are provided with a data structure containing details about employees, encompassing their distinct identification, significance level, and identification numbers. We have an employees array with each element structured as follows:

employees[i].id: This represents the identification number of the employee.
employees[i].importance: This denotes the level of importance of the employee.
employees[i].subordinates: This is an array listing the identification numbers of the subordinates of the employee.

Given an id that signifies an employee’s identification number, our task is to calculate the importance value associated with this employee, as well as all of their direct and indirect subordinates. In the above illustration, the importance of "ID 12" is "9". We added the importance of "ID 12" and its associated subordinates, like "ID 15", whose importance is "-4". For "ID 15," the total importance is "-4" because it isn't associated with other employees.

Solution

Let’s break down the process step by step:

We’ll define an Employee class to represent individual employees. Each employee has the attributes mentioned above.
We’ll create a recursive depth-first search function called employeeimportance that calculates the total importance of an employee and all their subordinates. This function takes the list of employees and the ID of the employee as parameters.
We’ll initialize the total importance with the importance of the current employee and then recursively calculate the importance of its subordinates.

The `dfs` function

The dfs function calculates the combined importance of an employee and their subordinates by traversing the hierarchy. Its process can be broken down into the following steps:

Begin with an employee ID and fetch the corresponding employee object from the dictionary.
Go through the subordinates of the current employee.
For each subordinate, recursively call the dfs function to calculate their importance.
Sum the importance of each subordinate to the total.
When a subordinate has no further subordinates, return their importance.
Return the total importance of the employee and their subordinates back to the main function.

This DFS approach efficiently computes the overall importance by summing up the importance of each employee and their respective subordinates in the hierarchical structure.

Code

The code for this problem is provided below:

class Employee:
    def __init__(self, id, importance, subordinates):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
def employeeimportance(employees, id):
    dictionary = {e.id: e for e in employees}
    
    def dfs(empid):
        employee = dictionary[empid]
        total = employee.importance
        for subid in employee.subordinates:
            total += dfs(subid)
        return total
    
    return dfs(id)
employee1 = Employee(2, 6, [1, 3])  #Employee(ID, Importance, [Associated Employee IDs])
employee2 = Employee(2, 4, [])
employee3 = Employee(1, 2, [])
employees = [employee1, employee2, employee3]
result = employeeimportance(employees, 1)
print(result)

Explanation

The above code can be explained as follows:

Lines 1–5: We define the Employee class with id, importance, and subordinates as its attributes.
Line 7: We define the employeeimportance function that takes id and employees as parameters.
Line 8: We create a dictionary and map employee IDs with their corresponding Employee objects.
Line 10: The dfs (depth-first search) function takes the employee’s ID as a parameter and retrieves the corresponding Employee object.
Line 12: We initialize total with the importance value of the current employee.
Lines 13–14: We iterate through the list of subordinates and recursively calculate the total importance of each subordinate by calling dfs(subid).
Line 17: We return the total importance.
Lines 19–25: We write the code for testing the function.

Note: You can alter the code at the end to test with your own values.

Free Resources