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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Employee Importance

Number: 690

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Uber

Problem Description

Given a list of employees where each employee has a unique ID, an importance value, and a list of direct subordinate IDs, calculate the total importance value of a given employee. This total includes the employee's own importance and the importance values of all their direct and indirect subordinates.

Key Insights

  • Map employee IDs to their corresponding employee object for quick lookup.
  • The problem can be modeled as a tree or graph where nodes represent employees.
  • Traverse the tree (using DFS or BFS) starting from the given employee ID.
  • Sum the importance values along the traversal path.
  • Handle potential negative importance values.

Space and Time Complexity

Time Complexity: O(n), where n is the number of employees, since in the worst case every employee will be visited. Space Complexity: O(n) in the worst case due to recursion call stack (DFS) or queue (BFS) and additional hashmap for storing employee lookup.

Solution

We first build a hashmap (or dictionary) mapping each employee's ID to the employee object for O(1) access during traversal. Then, using either Depth First Search (DFS) or Breadth First Search (BFS), we traverse from the target employee, and at each node we add its importance to a running total. The DFS approach can be implemented recursively or iteratively with a stack, while the BFS approach makes use of a queue. The key idea is ensuring that each employee is processed exactly once.

Code Solutions

# Define the Employee class (for context)
class Employee:
    def __init__(self, id, importance, subordinates):
        self.id = id                   # Unique employee ID
        self.importance = importance   # Importance value of the employee
        self.subordinates = subordinates  # List of subordinate IDs

def getImportance(employees, id):
    # Create a mapping from employee id to the employee object for quick lookup
    employee_map = {employee.id: employee for employee in employees}
    
    # Define a recursive DFS function
    def dfs(emp_id):
        current = employee_map[emp_id]  # Get current employee object using employee_map
        total = current.importance        # Start with current employee's importance
        
        # Recursively add importance from all direct subordinates
        for sub_id in current.subordinates:
            total += dfs(sub_id)         # Add the importance from subordinate subtree
        return total
    
    return dfs(id)  # Initiate DFS from the given employee id

# Example usage:
# employees = [Employee(1, 5, [2,3]), Employee(2, 3, []), Employee(3, 3, [])]
# print(getImportance(employees, 1))  # Output: 11
← Back to All Questions