We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Employee Importance

Difficulty: Medium

Problem Description

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs. Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.

Key Insights

  • Each employee has a unique ID and an importance value, along with a list of subordinate IDs.
  • The problem requires aggregating the importance values recursively, including all direct and indirect subordinates.
  • A depth-first search (DFS) or breadth-first search (BFS) approach can be used to traverse the employee hierarchy.
  • We can utilize a hash table (dictionary) to store the employees for quick access by their IDs.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of employees, as we may visit each employee once. Space Complexity: O(N) - for the hash table storing employee data and the recursion stack in the case of DFS.

Solution

To solve the problem, we can use a graph traversal technique, such as depth-first search (DFS). We will maintain a hash table (dictionary) that maps each employee's ID to their corresponding employee details. Starting from the given employee ID, we will recursively add up the importance values of the employee and all their subordinates until all reachable employees have been accounted for.

Code Solutions

class Employee:
    def __init__(self, id, importance, subordinates):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

def getImportance(employees, id):
    emp_dict = {employee.id: employee for employee in employees}  # Create a mapping from ID to Employee
    def dfs(emp_id):
        employee = emp_dict[emp_id]
        total_importance = employee.importance  # Start with the employee's own importance
        for sub_id in employee.subordinates:  # Traverse each subordinate
            total_importance += dfs(sub_id)  # Add their importance recursively
        return total_importance
    
    return dfs(id)  # Start DFS from the given employee ID
← Back to All Questions