Gui B.L Software Engineering-Code and posts about tech and programming

Get total count of employees under each manager in the hierarchy

10 April 2015

Problem overview

Given a dictionary that contains mapping of employee and his/her manager like this:

      Dictionary<string, string> employees = new Dictionary<>()
            {
                { "A","C" },
                { "B","C" },
                { "C","F" },
                { "D","E" },
                { "E","F" },
                { "F","F" }
            };

Write a function to get no of employees under each manager in the hierarchy not just their direct reports. In the above dictionary the root node/ceo is listed as reporting to himself.

Output should be a Dictionary<string,int> that contains this:

A - 0
B - 0
C - 2
D - 0
E - 1
F - 5

Algorithm analysis

Best data structure to model a hierarchy is a Tree, in this case based on the input data it would make it possible to build the tree in O(n) time, using a HashMap lets you jump directly to a node instead of traversing there from the tree's root node:

build tree of designated company hierarchy based on input map, use an auxiliary Map of <String, TreeNodeEmp> representing each employee and also for adding the direct employees of a specific manager. complexity: O(n)
Once tree is built, subsequent operations in hierarchy such as counting total direct and indirect employees of one specific manager becomes straightforward given any employee.

Code in Java

public class CountEmployeesHierarchyOrg {

<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">printAllEmployeesOfAllManagers</span><span class="o">();</span>     
<span class="o">}</span>


<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">printAllEmployeesOfAllManagers</span><span class="o">()</span> <span class="o">{</span>
    <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">String</span><span class="o">&gt;</span> <span class="n">dataSet</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o">&lt;&gt;();</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"A"</span><span class="o">,</span> <span class="s">"C"</span><span class="o">);</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"B"</span><span class="o">,</span> <span class="s">"C"</span><span class="o">);</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"C"</span><span class="o">,</span> <span class="s">"F"</span><span class="o">);</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"D"</span><span class="o">,</span> <span class="s">"E"</span><span class="o">);</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"E"</span><span class="o">,</span> <span class="s">"F"</span><span class="o">);</span>
    <span class="n">dataSet</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="s">"F"</span><span class="o">,</span> <span class="s">"F"</span><span class="o">);</span>

    <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">TreeNodeEmp</span><span class="o">&gt;</span> <span class="n">empTreeNodeMap</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o">&lt;&gt;();</span>
    <span class="n">TreeNodeEmp</span> <span class="n">root</span> <span class="o">=</span> <span class="n">buildHierarchyTreeOfCompany</span><span class="o">(</span><span class="n">dataSet</span><span class="o">,</span> <span class="n">empTreeNodeMap</span><span class="o">);</span>
    <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">Integer</span><span class="o">&gt;</span> <span class="n">output</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o">&lt;&gt;();</span>

    <span class="k">for</span> <span class="o">(</span><span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">TreeNodeEmp</span><span class="o">&gt;</span> <span class="n">empEntry</span> <span class="o">:</span> <span class="n">empTreeNodeMap</span>
            <span class="o">.</span><span class="na">entrySet</span><span class="o">())</span> <span class="o">{</span>
        <span class="n">String</span> <span class="n">empName</span> <span class="o">=</span> <span class="n">empEntry</span><span class="o">.</span><span class="na">getKey</span><span class="o">();</span>
        <span class="n">TreeNodeEmp</span> <span class="n">emp</span> <span class="o">=</span> <span class="n">empEntry</span><span class="o">.</span><span class="na">getValue</span><span class="o">();</span>
        <span class="n">output</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">empName</span><span class="o">,</span> <span class="n">getCountEmployeesOfManager</span><span class="o">(</span><span class="n">emp</span><span class="o">)</span> <span class="o">-</span> <span class="mi">1</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="n">printResults</span><span class="o">(</span><span class="n">output</span><span class="o">);</span>
<span class="o">}</span>

<span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">printResults</span><span class="o">(</span><span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">Integer</span><span class="o">&gt;</span> <span class="n">results</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">for</span> <span class="o">(</span><span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">Integer</span><span class="o">&gt;</span> <span class="n">r</span> <span class="o">:</span> <span class="n">results</span><span class="o">.</span><span class="na">entrySet</span><span class="o">())</span> <span class="o">{</span>
        <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">r</span><span class="o">.</span><span class="na">getKey</span><span class="o">()</span> <span class="o">+</span> <span class="s">" - "</span> <span class="o">+</span> <span class="n">r</span><span class="o">.</span><span class="na">getValue</span><span class="o">());</span>
    <span class="o">}</span>
<span class="o">}</span>

<span class="kd">public</span> <span class="kd">static</span> <span class="n">Integer</span> <span class="nf">getCountEmployeesOfManager</span><span class="o">(</span><span class="n">TreeNodeEmp</span> <span class="n">root</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">count</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
    <span class="k">for</span> <span class="o">(</span><span class="n">TreeNodeEmp</span> <span class="n">emp</span> <span class="o">:</span> <span class="n">root</span><span class="o">.</span><span class="na">children</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">count</span> <span class="o">+=</span> <span class="n">getCountEmployeesOfManager</span><span class="o">(</span><span class="n">emp</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="k">return</span> <span class="n">count</span><span class="o">;</span>
<span class="o">}</span>

<span class="kd">public</span> <span class="kd">static</span> <span class="n">TreeNodeEmp</span> <span class="nf">buildHierarchyTreeOfCompany</span><span class="o">(</span>
        <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">String</span><span class="o">&gt;</span> <span class="n">empMap</span><span class="o">,</span> <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">TreeNodeEmp</span><span class="o">&gt;</span> <span class="n">empTreeNodeMap</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">Map</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">TreeNodeEmp</span><span class="o">&gt;&gt;</span> <span class="n">auxMgrEmpList</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o">&lt;&gt;();</span>
    <span class="n">List</span><span class="o">&lt;</span><span class="n">TreeNodeEmp</span><span class="o">&gt;</span> <span class="n">listEmps</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">TreeNodeEmp</span> <span class="n">emp</span> <span class="o">=</span> <span class="kc">null</span><span class="o">,</span> <span class="n">mgr</span> <span class="o">=</span> <span class="kc">null</span><span class="o">,</span> <span class="n">root</span> <span class="o">=</span> <span class="kc">null</span><span class="o">;</span>
    <span class="n">String</span> <span class="n">nameEmp</span><span class="o">,</span> <span class="n">managerName</span><span class="o">;</span>

    <span class="k">for</span> <span class="o">(</span><span class="n">Map</span><span class="o">.</span><span class="na">Entry</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">String</span><span class="o">&gt;</span> <span class="n">empMapEntry</span> <span class="o">:</span> <span class="n">empMap</span><span class="o">.</span><span class="na">entrySet</span><span class="o">())</span> <span class="o">{</span>
            <span class="n">nameEmp</span> <span class="o">=</span> <span class="n">empMapEntry</span><span class="o">.</span><span class="na">getKey</span><span class="o">();</span>
            <span class="n">managerName</span> <span class="o">=</span> <span class="n">empMapEntry</span><span class="o">.</span><span class="na">getValue</span><span class="o">();</span>

            <span class="k">if</span> <span class="o">(!</span><span class="n">empTreeNodeMap</span><span class="o">.</span><span class="na">containsKey</span><span class="o">(</span><span class="n">nameEmp</span><span class="o">))</span> <span class="o">{</span>
                <span class="n">emp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">TreeNodeEmp</span><span class="o">(</span><span class="n">nameEmp</span><span class="o">,</span> <span class="n">managerName</span><span class="o">);</span>

                <span class="c1">// check for who was added before and have this as a manger</span>
                <span class="k">if</span><span class="o">(</span><span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">containsKey</span><span class="o">(</span><span class="n">nameEmp</span><span class="o">))</span> <span class="o">{</span>
                   <span class="n">emp</span><span class="o">.</span><span class="na">children</span><span class="o">.</span><span class="na">addAll</span><span class="o">(</span><span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">nameEmp</span><span class="o">));</span>  
                <span class="o">}</span>                                        
                <span class="n">empTreeNodeMap</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">nameEmp</span><span class="o">,</span> <span class="n">emp</span><span class="o">);</span>
            <span class="o">}</span>

            <span class="k">if</span> <span class="o">(</span><span class="n">nameEmp</span><span class="o">.</span><span class="na">equals</span><span class="o">(</span><span class="n">managerName</span><span class="o">))</span> <span class="o">{</span>
                <span class="n">root</span> <span class="o">=</span> <span class="n">emp</span><span class="o">;</span>
            <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(</span><span class="n">empTreeNodeMap</span><span class="o">.</span><span class="na">containsKey</span><span class="o">(</span><span class="n">managerName</span><span class="o">))</span> <span class="o">{</span>
                <span class="n">mgr</span> <span class="o">=</span> <span class="n">empTreeNodeMap</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">managerName</span><span class="o">);</span>
                <span class="n">mgr</span><span class="o">.</span><span class="na">children</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">emp</span><span class="o">);</span>
            <span class="o">}</span> <span class="k">else</span> <span class="k">if</span> <span class="o">(!</span><span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">containsKey</span><span class="o">(</span><span class="n">managerName</span><span class="o">)){</span>
                <span class="n">listEmps</span> <span class="o">=</span> <span class="k">new</span> <span class="n">ArrayList</span><span class="o">&lt;&gt;();</span>
                <span class="n">listEmps</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">emp</span><span class="o">);</span>
                <span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">managerName</span><span class="o">,</span> <span class="n">listEmps</span><span class="o">);</span>
            <span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
                <span class="n">listEmps</span> <span class="o">=</span> <span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">get</span><span class="o">(</span><span class="n">managerName</span><span class="o">);</span>
                <span class="n">listEmps</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">emp</span><span class="o">);</span>
                <span class="n">auxMgrEmpList</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">managerName</span><span class="o">,</span> <span class="n">listEmps</span><span class="o">);</span>                  
            <span class="o">}</span>

    <span class="o">}</span>

    <span class="k">return</span> <span class="n">root</span><span class="o">;</span>
<span class="o">}</span>


}

class TreeNodeEmp {
    String name;
    String managerName;
    Set<TreeNodeEmp> children;

<span class="kd">public</span> <span class="nf">TreeNodeEmp</span><span class="o">(</span><span class="n">String</span> <span class="n">name</span><span class="o">,</span> <span class="n">String</span> <span class="n">managerName</span><span class="o">)</span> <span class="o">{</span>
    <span class="k">this</span><span class="o">.</span><span class="na">name</span> <span class="o">=</span> <span class="n">name</span><span class="o">;</span>
    <span class="k">this</span><span class="o">.</span><span class="na">managerName</span> <span class="o">=</span> <span class="n">managerName</span><span class="o">;</span>
    <span class="n">children</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashSet</span><span class="o">&lt;&gt;();</span>
<span class="o">}</span>


}

Full source code