2
\$\begingroup\$

You are given a data structure 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.

Please comment about performance.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace GraphsQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/employee-importance/
    /// </summary>
    [TestClass]
    public class EmployeeImportanceBFS
    {
        [TestMethod]
        public void ChildrenSumTo30Test()
        {
            List<Employee> employees = new List<Employee>();
            Employee one = new Employee { Id = 1, Importance = 15 };
            Employee two = new Employee { Id = 2, Importance = 10 };
            one.Subordinates.Add(two.Id);
            Employee three = new Employee { Id = 3, Importance = 5 };
            two.Subordinates.Add(three.Id);
            employees.Add(one);
            employees.Add(two);
            employees.Add(three);
            Assert.AreEqual(30, GetImportance(employees, 1));
        }

        [TestMethod]
        public void ChildrenSumTo11Test()
        {
            List<Employee> employees = new List<Employee>();
            Employee one = new Employee { Id = 1, Importance = 5 };
            Employee two = new Employee { Id = 2, Importance = 3 };
            Employee three = new Employee { Id = 3, Importance = 3 };
            one.Subordinates.Add(three.Id);
            one.Subordinates.Add(two.Id);
            employees.Add(one);
            employees.Add(two);
            employees.Add(three);
            Assert.AreEqual(11, GetImportance(employees, 1));
        }

        int GetImportance(IList<Employee> employees, int id)
        {
            Dictionary<int, Employee> idToEmployee = new Dictionary<int, Employee>();
            foreach (var employee in employees)
            {
                idToEmployee.Add(employee.Id, employee);
            }

            int result = 0;
            if (employees == null || employees.Count == 0)
            {
                return result;
            }
            Queue<Employee> Q = new Queue<Employee>();
            Q.Enqueue(idToEmployee[id]);
            while (Q.Count > 0)
            {
                var current = Q.Dequeue();
                result += current.Importance;
                foreach (var childIdSubordinate in current.Subordinates)
                {
                    if (idToEmployee.ContainsKey(childIdSubordinate))
                    {
                        Q.Enqueue(idToEmployee[childIdSubordinate]);
                    }
                }
            }

            return result;
        }
    }



    // Employee info
    class Employee
    {
        public Employee()
        {
            Subordinates = new List<int>();
        }
        // It's the unique ID of each node.
        // unique id of this employee
        public int Id { get; set; }
        // the importance value of this employee
        public int Importance { get; set; }
        // the id of direct subordinates
        public List<int> Subordinates { get; set; }
    }

}
\$\endgroup\$
5
\$\begingroup\$

You'll have to have this check before the initialization of the dictionary:

  if (employees == null || employees.Count == 0)
  {
    return 0;
  }

or else the initialization of the dictionary may throw if employees == null


You can initialize the dictionary this way:

Dictionary<int, Employee> idToEmployee = employees.ToDictionary(e => e.Id);

Instead of:

if (idToEmployee.ContainsKey(childIdSubordinate))
  {
    Q.Enqueue(idToEmployee[childIdSubordinate]);
  }

You can do:

      if (idToEmployee.TryGetValue(childIdSubordinate, out Employee subordinate))
      {
        Q.Enqueue(subordinate);
      }
\$\endgroup\$
  • \$\begingroup\$ I think the TryGetValue needs explanation that it's not just an alternative technique but is more efficient since it queries the dictionary once instead of twice. \$\endgroup\$ – Rick Davin May 8 at 12:45
  • \$\begingroup\$ @RickDavin: One should think so, but according to the reference it actually does the same as when using ContainsKey etc. - it just combines them into one method. \$\endgroup\$ – Henrik Hansen May 8 at 13:07
  • 1
    \$\begingroup\$ @HenrikHansen it only calls FindEntry once, which is the expensive bit. (As opposed to calling ContainsKey and this[TKey] which both call it). \$\endgroup\$ – VisualMelon May 8 at 16:40
  • 1
    \$\begingroup\$ @RickDavin: You're right - I didn't check this[] \$\endgroup\$ – Henrik Hansen May 8 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.