Employee Importance - Practice Coding Problems

Employee Importance - Problem

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees employees where:

employees[i].id is the ID of the i^th employee
employees[i].importance is the importance value of the i^th employee
employees[i].subordinates is a list of the IDs of the direct subordinates of the i^th employee

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.

Input & Output

Example 1 — Basic Hierarchy

$ Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1

› Output: 11

💡 Note: Employee 1 has importance 5, and has two direct subordinates 2 and 3. Employee 2 has importance 3, employee 3 has importance 3. Total: 5 + 3 + 3 = 11.

Example 2 — Single Employee

$ Input: employees = [[1,2,[5]],[5,1,[]]], id = 5

› Output: 1

💡 Note: Employee 5 has importance 1 and no subordinates. Total importance is just 1.

Example 3 — Deep Hierarchy

$ Input: employees = [[1,5,[2]],[2,3,[3]],[3,4,[]]], id = 1

› Output: 12

💡 Note: Employee 1 has subordinate 2, employee 2 has subordinate 3. Total: 5 + 3 + 4 = 12.

Constraints

1 ≤ employees.length ≤ 2000
1 ≤ employees[i].id ≤ 2000
0 ≤ employees[i].importance ≤ 1000
One employee has at most one direct leader and may have several subordinates
The IDs in employees[i].subordinates are valid IDs

Visualization

Tap to expand

Understanding the Visualization

Input

Employee array with ID, importance, and subordinate relationships

Process

Traverse hierarchy from given employee ID downward

Output

Sum of importance values for employee and all subordinates

Key Takeaway

🎯 Key Insight: Use hash map for O(1) employee lookup and tree traversal (DFS/BFS) to visit all subordinates

Asked in

G Google 12 a Amazon 8 M Microsoft 5 f Facebook 4

The key insight is to treat the employee structure as a tree and traverse from the target employee to all subordinates. The optimal approach uses a hash map for O(1) employee lookup combined with DFS or BFS traversal. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map + DFS	O(n)	O(n)	Build employee ID map first, then use DFS to traverse hierarchy efficiently
Brute Force Linear Search	O(n²)	O(h)	For each subordinate, search through entire employees array to find their data
BFS with Queue	O(n)	O(n)	Use breadth-first search with a queue to traverse the employee hierarchy level by level

Hash Map + DFS — Algorithm Steps

Build hash map: id -> employee object
Start DFS from given employee ID
For each employee, add their importance
Recursively process all subordinates using map lookup

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Create hash map: ID -> Employee for O(1) lookup

DFS Traversal

Use map to quickly find each employee during traversal

Sum Values

Add importance values from all subordinates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_EMPLOYEES 1000
#define MAX_SUBORDINATES 100
#define HASH_SIZE 10007

typedef struct {
    int id;
    int importance;
    int subordinates[MAX_SUBORDINATES];
    int subCount;
} Employee;

typedef struct HashNode {
    int key;
    Employee* emp;
    struct HashNode* next;
} HashNode;

Employee employees[MAX_EMPLOYEES];
HashNode* hashTable[HASH_SIZE];
int empCount = 0;

int hash(int key) {
    return ((key % HASH_SIZE) + HASH_SIZE) % HASH_SIZE;
}

void insertHash(int key, Employee* emp) {
    int idx = hash(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->emp = emp;
    node->next = hashTable[idx];
    hashTable[idx] = node;
}

Employee* findEmployee(int empId) {
    int idx = hash(empId);
    HashNode* node = hashTable[idx];
    while (node) {
        if (node->key == empId) {
            return node->emp;
        }
        node = node->next;
    }
    return NULL;
}

int dfs(int empId) {
    Employee* emp = findEmployee(empId);
    if (!emp) return 0;
    
    int total = emp->importance;
    for (int i = 0; i < emp->subCount; i++) {
        total += dfs(emp->subordinates[i]);
    }
    return total;
}

int solution(int id) {
    return dfs(id);
}

int main() {
    // Initialize hash table
    memset(hashTable, 0, sizeof(hashTable));
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line + 1;
    empCount = 0;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            Employee* emp = &employees[empCount++];
            ptr++;
            
            emp->id = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            
            emp->importance = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            
            ptr++;
            emp->subCount = 0;
            while (*ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    emp->subordinates[emp->subCount++] = atoi(ptr);
                    while (*ptr >= '0' && *ptr <= '9') ptr++;
                } else {
                    ptr++;
                }
            }
            ptr++;
            
            // Insert into hash table
            insertHash(emp->id, emp);
        }
        ptr++;
    }
    
    int id;
    scanf("%d", &id);
    
    int result = solution(id);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

O(n) to build map + O(n) to visit each employee once during DFS

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all n employees + O(h) recursion stack

⚡ Linearithmic Space

38.6K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map + DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler