algoadvance

Leetcode 690. Employee Importance

Problem Statement

You are given a data structure of employee information, which includes the employee’s unique id, their importance value, and their direct subordinates’ ids.

You are asked to implement a function that takes two arguments, a list of employees and an integer id. The list of employees contains Employee objects. Each Employee object has the following attributes:

The goal of the function is to return the total importance value of the employee with the given id, along with all their subordinates’ importance values.

Here is how the Employee class is defined:

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

Clarifying Questions

  1. Input Validation: Should I assume that the inputs are always valid, or do I need to handle cases where the given id does not exist in the list of employees?
  2. Unique IDs: Can I assume that all employee IDs are unique?
  3. Non-empty List: Can the employees list be empty?

(Assuming positive answers for clarification 1 and 2, and handling the edge case for 3.)

Strategy

To solve this problem, we will use a Depth-First Search (DFS) approach. Here’s the step-by-step strategy:

  1. Create a Mapping: Create a hash map (or unordered_map) to easily access any employee’s data using their id.
  2. DFS Function: Implement a helper DFS function to recursively compute the total importance value by traversing through each employee’s subordinates.
  3. Base Case and Recursion: In the DFS function, for each subordinate, call the DFS function recursively to accumulate their importance values.

Code

#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        // Create a map for quick lookup of employee by id
        unordered_map<int, Employee*> employeeMap;
        for (auto employee : employees) {
            employeeMap[employee->id] = employee;
        }
        
        // DFS function to calculate total importance
        function<int(int)> dfs = [&](int employeeId) -> int {
            Employee* employee = employeeMap[employeeId];
            int totalImportance = employee->importance;
            for (int subId : employee->subordinates) {
                totalImportance += dfs(subId);
            }
            return totalImportance;
        };
        
        // Start DFS from the given employee id
        return dfs(id);
    }
};

Time Complexity

This ensures that the solution is efficient and scales well with the size of the input.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI