Hackbright Code Challenges

Count Employees

Count Employees

Whiteboard

Harder

Challenge

Medium

Concepts

Recursion, Trees

Download

count-employees.zip

Solution

Count Employees: Solution


Consider an organization chart like:

digraph emps { rankdir=TB Jane -> { Jessica, Janet } Jessica -> { Al, Bob, Jen } Janet -> { Nick, Nora } Nora -> Henri }

This can be represented using nodes in a tree, like this:

>>> henri = Node("Henri")
>>> nora = Node("Nora", [henri])
>>> nick = Node("Nick")
>>> janet = Node("Janet", [nick, nora])
>>> al = Node("Al")
>>> bob = Node("Bob")
>>> jen = Node("Jen")
>>> jessica = Node("Jessica", [al, bob, jen])
>>> jane = Node("Jane", [jessica, janet])

Our Node class is:

class Node(object):
    """Node in a tree."""

    def __init__(self, name, children=None):
        self.name = name
        self.children = children or []

We want to create a method of our Node class, count_employees, which returns a count of how many employees this person manages.

This should include everyone under them, not just people who directly report to them.

For three chart above, this would return 0 for Henri, 1 for Nona, and 8 for Jane.

We’ve provided a file, countemployees.py, with doctests. These currently fail.

It has a stub implementation of the count_employees:

class Node(object):   # ...
    def count_employees(self):
        """Return a count of how many employees this person manages.

        Return a count of how many people that manager manages. This should
        include *everyone* under them, not just people who directly report to
        them.
        """

Implement the count_employees method. When this is successful, all tests should pass.

Hint

Recursion

This problem is easiest solved with recursion.