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: 11Explanation:
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<int> 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<int> 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;
}
};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<Integer> 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<Integer> 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;
}
}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<int> 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<int> 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;
}
};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<Integer> 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<Integer> 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;
}
}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) —
loading...
Last Post: Computing History Museum
Next Post: The Jumping Kangaroo Problem (Dynamic Programming + Greedy Algorithm)
