Login and get codingOf all the types of questions you are likely to encounter during a technical interview - assuming the interview is focused on data structures and algorithms - those related to 'trees' and 'graphs' are arguably the most common.
Although a full discussion of graph theory is beyond the scope of this Bite, any such discussion begins with trees, which is where we'll start.
Trees
In computer science, tree, is an abstract data structure often used to model hierarchical relationships and resembling, more or less, an actual tree in nature - excepted inverted, with its root at the top and leaves at the bottom.
A tree consists of nodes connected by edges.
A node, in turn, stores data (of any type) as well as pointers to other nodes. A node's nodes are called its children, and a node with no children is called a leaf.
Binary Trees
A binary tree is a type of tree with a specific constraint - each node in a binary tree can have a maximum of two children.
Here a picture may help:
This tree has a depth of three and consists of the following:
- O -> root node with two children, 1 and 2.
- 1 -> node with two children, 3 and 4.
- 3 -> a leaf (node with no children)
- 4 -> leaf
- 2 -> child node of 0 with one child, 5.
- 5 -> leaf
Exercise
Given a company org chart, determine the maximum depth of the organizational tree.
- The org chart can be of any size.
- The org chart is represented as a Python
list
(more below).- You are given one class and one function to start.
class EmployeeNode
- This class defines a node in the organizational tree. Each node represents an employee's role (or name). The node can have two children:
left
andright
, representing two direct reports of that employee. By default, these are set toNone
. Each node also has avalue
, which is the role (or name) of the employee.build_org_chart()
- The purpose of this function is to build an organizational tree (binary tree) from a given list. Each item in the list is either a role of an employee or
None
(indicating an empty position). This function uses a queue to process each node in a level-order fashion. For every node, it will set its left and right children based on the next two values from the list. The function returns the root node of this tree.Learner's Task
- Write a function -
max_depth()
- that calculates the maximum depth of a given organizational tree.Example
- Given the list
["CEO", "CFO", None, "COO", None, None, "CTO"]
, thebuild_org_chart()
function will build (a serialized version of) the tree below, and return3
because the tree has 3 levels (i.e. a depth of 3).
>>> from org_chart import build_org_chart, max_depth
>>> org_list = ["CEO", "CFO", None, "COO", None, None, "CTO"]
>>> org_structure = build_org_chart(org_list)
>>> max_depth(org_structure)
See also the tests for more scenarios ...
Keep calm and code in Python!
10 out of 14 users completed this Bite.
Will you be the 11th person to crack this Bite?
Resolution time: ~41 min. (avg. submissions of 5-240 min.)
Our community rates this Bite 3.67 on a 1-10 difficulty scale.
» You can do it! 😌