Employee Importance


  • 0

    Click here to see the full article post


  • 0
    S

    appreciate it!


  • 0
    R

    My Java Solution

     public int getImportance(List<Employee> employees, int id) {
            int sum = 0;
            Employee target = null;
            for(Employee e : employees){
                if(e.id == id) target = e;
            }
            for(int i = 0; i < target.subordinates.size(); ++i){
                sum += getImportance(employees, target.subordinates.get(i));
            }
            return target.importance + sum;
        }
    

  • 0

    Here is a solution without a global variable.

    public int getImportance(List<Employee> employees, int id) {
        final Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        } 
        
        return getImportance(map, id);
    }
    
    private int getImportance(Map<Integer, Employee> map, int id) {
        final Employee employee = map.get(id);
        int importance = employee.importance;
        for (Integer number : employee.subordinates) {
            importance += getImportance(map, number);
        }
        
        return importance;
    }

  • 0

    My Python solution.

    class Solution(object):
        def getImportance(self, employees, id):
            """
            :type employees: Employee
            :type id: int
            :rtype: int
            """ 
            emap = {e.id: e for e in employees}
            employee = emap[id]
            total_importance = employee.importance    
            
            for id in employee.subordinates:
                total_importance += self.getImportance(employees, id)
                
            return total_importance
    

  • 0
    H

    Python Solution
    class Solution(object):
    def getImportance(self, employees, id):
    """
    :type employees: Employee
    :type id: int
    :rtype: int
    """
    dic = {employee.id: employee for employee in employees}
    return dic[id].importance + sum([self.getImportance(employees, subid) for subid in dic[id].subordinates])


  • 0
    J

    Java Solution using Streams API

    import java.util.List;
    import java.util.Map;
    import java.util.function.Function;
    import java.util.stream.Collectors;
    
    class Solution 
    {
        public int getImportance(List<Employee> employees, int id)
        {
            return _getImportance(employees.stream().collect(Collectors.toMap((Employee e) -> e.id , Function.identity())), id);
        }
    
        private int _getImportance(Map<Integer, Employee> employeeById, int id)
        {
            return employeeById.get(id).importance + employeeById.get(id).subordinates.stream().mapToInt(subId -> _getImportance(employeeById, subId)).sum();
        }
    }
    

  • 0
    A

    Java iterative solution

    class Solution {
        public int getImportance(List<Employee> employees, int id) {
            int result = 0;
            Map<Integer, Employee> m = new HashMap<>();
            Queue<Employee> q = new LinkedList<>();
            
            for (int i=0; i<employees.size(); i++){
                m.put(employees.get(i).id, employees.get(i));
            }
            q.add(m.get(id));
            
            while(!q.isEmpty()){
                Employee e = q.poll();
                for(int i=0; i<e.subordinates.size();i++){
                    q.add(m.get(e.subordinates.get(i)));
                }
                result += e.importance;
            }
            
            return result;
        }
    }
    

  • 0
    J

    class Solution {
    private int getValue(Map<Integer, Employee>m ,Employee employee, int value) {
    value += employee.importance;
    for (Integer sudId : employee.subordinates) {
    value = getValue(m, m.get(sudId), value);
    }
    return value;
    }

    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> m = employees.stream().collect(Collectors.toMap(e -> e.id, Function.identity()));
        Employee employee = m.get(id);
        return getValue(m, employee, 0);
                
    
    }
    

    }


  • 0
    F

    Just want to double check, what if one employee reports to more than one person directly? In this case, need a set to memorize the already calculated persons.


  • 0
    D

    JIN11234567 you made some typos

    value += employee.importance;
    should be
    value = employee.importance;

    value = getValue(m, m.get(sudId), value);
    should be
    value += getValue(m, m.get(sudId), value);

    I haven't seen anything like that stream though in getImportance that's pretty cool :)


  • 0
    Q

    Python solution is elegant,

    Thanks a lot!


  • 0
    L

    python is good for recursion


  • 0
    P

    Variation of DFS:

    /*
    // 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 {
        int sum = 0;
        List<Integer> subordinatesList = new ArrayList<>();
        public int getImportance(List<Employee> employees, int id) {
            findSub(employees, id);
            System.out.println(subordinatesList);
            
            for (Employee emp: employees){            
                if (subordinatesList.contains(emp.id)){
                    sum = sum + emp.importance;
                }            
            }                        
            return sum;
        }
        
        public void findSub(List<Employee> ep,int id){
            
            for (Employee emp1 : ep){            
                if (emp1.id == id){
                    if (!subordinatesList.contains(id)){subordinatesList.add(id);}
                    
                    for (Integer int1 : emp1.subordinates){                    
                        if (!subordinatesList.contains(int1)){                        
                            subordinatesList.add(int1);
                            findSub(ep,int1);
                        }                                                                                
                    }                                                
                }            
            }                                        
        }
    }
    

  • 0
    P

    @flyyee0721
    In this problem one employee is not reporting to multiple people directly.
    But if we consider that case as a different problem then yes we need to have memoization of which employees have already been visited. That can be done with a HashSet to check if the employee has been visited or not.
    Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.