Employee Importance
Problem
Each Employee has id, importance, and list of subordinate ids. Sum the importance of an employee and all (transitive) subordinates.
employees=[[1,5,[2,3]],[2,3,[]],[3,3,[]]] id=111def get_importance(emps, eid):
by_id = {e[0]: e for e in emps}
total = 0; q = [eid]
while q:
e = by_id[q.pop()]; total += e[1]; q.extend(e[2])
return totalfunction getImportance(emps, eid) {
const m = new Map(emps.map(e => [e[0], e]));
let total = 0; const q = [eid];
while (q.length) { const e = m.get(q.pop()); total += e[1]; q.push(...e[2]); }
return total;
}int getImportance(List emps, int eid) {
Map m = new HashMap<>();
for (Employee e : emps) m.put(e.id, e);
int total = 0; Deque q = new ArrayDeque<>(); q.push(eid);
while (!q.isEmpty()) {
Employee e = m.get(q.pop());
total += e.importance; for (int s : e.subordinates) q.push(s);
}
return total;
} int getImportance(vector emps, int eid) {
unordered_map m;
for (auto e : emps) m[e->id] = e;
int total = 0; stack q; q.push(eid);
while (!q.empty()) {
Employee* e = m[q.top()]; q.pop();
total += e->importance; for (int s : e->subordinates) q.push(s);
}
return total;
} Explanation
We want the total importance of one employee plus everyone under them, however deep the chain goes. This is a graph traversal where employees are nodes and "manages" links are edges.
First the code builds a hash map by_id from employee id to that employee's record, so we can jump to anyone's data instantly given just an id (the subordinate lists only store ids).
Then it does a simple traversal with a stack q. It pops an employee, adds their importance to total, and pushes all their subordinate ids back onto the stack to be processed next.
Example: employee 1 has importance 5 and subordinates [2, 3], each worth 3. Starting at 1: total becomes 5, then we visit 2 (total 8) and 3 (total 11). Answer: 11.
Because every employee in the hierarchy is visited exactly once and looked up in O(1), the whole sum is collected in one pass over the subtree.