You are given a data structu re of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct. Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11

Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:
One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won’t exceed 2000.

The above problem can be converted equally to summing up the values of given tree and its sub trees. Almost all tree problems can be solved via DFS (Depth First Search) or BFS (Breadth First Search) algorithms.

DFS Depth First Search

The input data is an array of tree nodes with IDs (which may not come in orders), therefore, we need to first scan the array and put them in a hash map (unordered_map) so that we can access the node by ID later.

The next is to have another hashmap e.g. cached to store the values that have been computed when navigating the tree. The C++ DFS implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        for (const auto &e: employees) {
            emp[e->id] = e;
        }
        return dfs(id);
    }
private:
    unordered_map<int, int> cached;
    unordered_map<int, Employee*> emp;
    
    int dfs(int id) {
        if (emp.find(id) == emp.end()) return 0;
        // we have computed this before, so no need to compute again
        if (cached.find(id) != cached.end()) return cached[id];
        int r = emp[id]->importance;
        for (auto e: emp[id]->subordinates) {
            r += dfs(e);   
        };
        cached[id] = r; // store the value
        return r;        
    }
};
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector subordinates;
};
*/
class Solution {
public:
    int getImportance(vector employees, int id) {
        for (const auto &e: employees) {
            emp[e->id] = e;
        }
        return dfs(id);
    }
private:
    unordered_map cached;
    unordered_map emp;
    
    int dfs(int id) {
        if (emp.find(id) == emp.end()) return 0;
        // we have computed this before, so no need to compute again
        if (cached.find(id) != cached.end()) return cached[id];
        int r = emp[id]->importance;
        for (auto e: emp[id]->subordinates) {
            r += dfs(e);   
        };
        cached[id] = r; // store the value
        return r;        
    }
};

The DFS involves using stack, but this can be done via Recursion, which is usually easier to implement – the compiler maintains a stack i.e. calling a function is like pushing a EBP/ESP pointer to the stack.

Since the data structure is a tree. It makes sense that each node is visited at most once. Thus, we might not need a hashmap to cached the computed nodes. Here is a Java implementation that implements the Depth First Search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap();
        for (Employee e: employees) {
           emp.put(e.id, e);
        }
        return dfs(emp, id);
    }
    
    private int dfs(Map<Integer, Employee> emp, int id) {
        if (!emp.containsKey(id)) return 0;
        int r = emp.get(id).importance;
        for (int i: emp.get(id).subordinates) {
            r += dfs(emp, i);
        }
        return r;
    }
}
/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List subordinates;
};
*/
class Solution {
    public int getImportance(List employees, int id) {
        Map emp = new HashMap();
        for (Employee e: employees) {
           emp.put(e.id, e);
        }
        return dfs(emp, id);
    }
    
    private int dfs(Map emp, int id) {
        if (!emp.containsKey(id)) return 0;
        int r = emp.get(id).importance;
        for (int i: emp.get(id).subordinates) {
            r += dfs(emp, i);
        }
        return r;
    }
}

BFS Breadth First Search

The BFS requires a queue. You push the root node to the queue, and its children nodes at each iteration when popping one from the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        for (const auto &e: employees) {
            emp[e->id] = e;
        }
        return bfs(id);
    }
private:
    unordered_map<int, Employee*> emp;
    
    int bfs(int id) {
        if (emp.find(id) == emp.end()) return 0;
        queue<Employee*> Q;
        Q.push(emp[id]);
        int r = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            r += p->importance;
            for (const auto &n: p->subordinates) {
                if (emp.find(n) != emp.end()) {
                    Q.push(emp[n]);
                }  
            }
        }
        return r;        
    }
};
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector subordinates;
};
*/
class Solution {
public:
    int getImportance(vector employees, int id) {
        for (const auto &e: employees) {
            emp[e->id] = e;
        }
        return bfs(id);
    }
private:
    unordered_map emp;
    
    int bfs(int id) {
        if (emp.find(id) == emp.end()) return 0;
        queue Q;
        Q.push(emp[id]);
        int r = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            r += p->importance;
            for (const auto &n: p->subordinates) {
                if (emp.find(n) != emp.end()) {
                    Q.push(emp[n]);
                }  
            }
        }
        return r;        
    }
};

The time complexity is O(N) i.e. visiting each node exactly once. The Java implementation (as a good Java coding exercise) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap();
        for (Employee e: employees) {
           emp.put(e.id, e);
        }
        if (!emp.containsKey(id)) return 0;
        Queue<Employee> Q = new LinkedList();
        Q.add(emp.get(id)); // push the 'root' of the sub-tree into the queue
        int r = 0;
        while (!Q.isEmpty()) {
            Employee p = Q.peek();
            Q.poll();
            r += p.importance;
            for (int x: p.subordinates) {   // expand the child nodes             
                if (emp.containsKey(x)) {
                    Q.add(emp.get(x));
                }
            }
        }
        return r;
    }
}
/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List subordinates;
};
*/
class Solution {
    public int getImportance(List employees, int id) {
        Map emp = new HashMap();
        for (Employee e: employees) {
           emp.put(e.id, e);
        }
        if (!emp.containsKey(id)) return 0;
        Queue Q = new LinkedList();
        Q.add(emp.get(id)); // push the 'root' of the sub-tree into the queue
        int r = 0;
        while (!Q.isEmpty()) {
            Employee p = Q.peek();
            Q.poll();
            r += p.importance;
            for (int x: p.subordinates) {   // expand the child nodes             
                if (emp.containsKey(x)) {
                    Q.add(emp.get(x));
                }
            }
        }
        return r;
    }
}

The idea is the same in Java but there are quite a few syntax difference. Surprisingly, the Java solutions are running slightly faster than the C++ equivalences on the online judge server.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading…

1026 words
– Support my work via Donations (Thanks): Last Post: Computing History Museum
Next Post: The Jumping Kangaroo Problem (Dynamic Programming + Greedy Algorithm)





Source link

Leave a Reply

Your email address will not be published. Required fields are marked *