InterviewDB
Question
Employee Tree - Serialize and Traverse an Organizational Hierarchy
Onsite
Question Details
Problem
You are given a flat list of employees with {id, name, manager_id}. Build the org-chart tree and implement:
depth(employee_id) -> int: levels below root (root = 0).subtree_size(employee_id) -> int: number of nodes in the subtree rooted at that employee (inclusive).lowest_common_manager(id1, id2) -> int: the deepest manager who is an ancestor of both.serialize() -> str: BFS-order JSON representation of the tree.
python
class OrgChart:
def __init__(self, employees: List[dict]): ...
def depth(self, employee_id: int) -> int: ...
def subtree_size(self, employee_id: int) -> int: ...
def lowest_common_manager(self, id1: int, id2: int) -> int: ...
Example:
employees = [
{"id": 1, "manager_id": None},
{"id": 2, "manager_id": 1},
{"id": 3, "manager_id": 1},
{"id": 4, "manager_id": 2}
]
depth(4) -> 2
subtree_size(1) -> 4
lowest_common_manager(3, 4) -> 1
Follow-ups
- What is the time complexity of
lowest_common_manager? Can you get it to O(log n)? - How would you rebalance the tree if the org chart is very deep (degenerate chain)?
- How would you support moving a subtree to a new manager?
- How does this change if one employee can have multiple managers (matrix org)?
Full Details
Problem
You are given a flat list of employees with {id, name, manager_id}. Build the org-chart tree and implement:
depth(employee_id) -> int: levels below root (root = 0).subtree_size(employee_id) -> int: number of nodes in the subtree rooted at that employee (inclusive).lowest_common_manager(id1, id2) -> int: the deepest manager who is an ancestor of both.serialize() -> str: BFS-order JSON representation of the tree.
python
class OrgChart:
def __init__(self, employees: List[dict]): ...
def depth(self, employee_id: int) -> int: ...
def subtree_size(self, employee_id: int) -> int: ...
def lowest_common_manager(self, id1: int, id2: int) -> int: ...
Example:
employees = [
{"id": 1, "manager_id": None},
{"id": 2, "manager_id": 1},
{"id": 3, "manager_id": 1},
{"id": 4, "manager_id": 2}
]
depth(4) -> 2
subtree_size(1) -> 4
lowest_common_manager(3, 4) -> 1
Follow-ups
- What is the time complexity of
lowest_common_manager? Can you get it to O(log n)? - How would you rebalance the tree if the org chart is very deep (degenerate chain)?
- How would you support moving a subtree to a new manager?
- How does this change if one employee can have multiple managers (matrix org)?
Free preview. Unlock all C3 AI questions →
About This Question
This is a reported interview question from a c3 ai interview during the onsite round.
It covers the following topics: Coding, Graph, Onsite, Matrix .