Solution for Problem 1 of the Google technical interview
Problem 1
Given a class Company, implement the following functions:
def manager(employee: str, manager: str) -> None:
"""
Indicates that employee is a direct report of manager.
"""
def peer(employee: str, other: str) -> None:
"""
Indicates that employee and other are peers (same manager).
"""
def reports_to(employee: str, other: str) -> bool:
"""
Returns True if employee reports directly or indirectly to other, otherwise
returns False.
"""
Solution
This is a simple tree problem. Company is an n-ary tree. The operations manager() and peer() add nodes to the tree. The operation reports_to() is a straightforward tree traversal.
Why is this a tree problem?
The problem can be modeled using a tree because the relationships of the entities (manager, employee, and peer) adhere to its properties, namely, that each node in the tree can be connected to zero or more children, but each node has exactly one parent. From this we can make the following assertions:
- Each node is an employee.
- Edges represent reporting relationships.
- The root is the top-level manager.
- Peer relationships can be derived by finding nodes that share the same parent (manager).
Initially, I used a hash table to keep track of nodes, however, this is unnecessary, since a node only needs to store its value and references to other nodes.
A node (employee) can be represented with the following class:
class Employee:
def __init__(self, id: str) -> None:
self.id: str = id
self.manager: Employee | None = None
self.employees: list[Employee] = []
"""
Solutions for the Google technical interview
"""
class Employee:
def __init__(self, employee_id: str) -> None:
self.employee_id = employee_id
self.manager: Employee | None = None
self.employees: list[Employee] = []
class Company:
def __init__(self) -> None:
self.employees: dict[str, Employee] = {}
def manager(self, employee: str, manager: str) -> None:
"""
Indicates that employee is a direct report of manager.
"""
e, m = self.employees.get(employee), self.employees.get(manager)
if not e:
e = Employee(employee_id=employee)
self.employees[employee] = e
if not m:
m = Employee(employee_id=manager)
self.employees[manager] = m
e.manager = m
m.employees.append(e)
def peer(self, employee: str, other: str) -> None:
"""
Indicates that employee and other are peers (same manager).
"""
e, o = self.employees.get(employee), self.employees.get(other)
if not e:
e = Employee(employee_id=employee)
self.employees[employee] = e
if not o:
o = Employee(employee_id=other)
self.employees[other] = o
if e.manager:
o.manager = e.manager
e.manager.employees.append(o)
elif o.manager:
e.manager = o.manager
o.manager.employees.append(e)
def reports_to(self, employee: str, other: str) -> bool:
"""
Returns True if employee reports directly or indirectly to other,
otherwise returns False.
"""
e, o = self.employees.get(employee), self.employees.get(other)
if not e or not o:
return False
while e:
if e == o:
return True
e = e.manager
return False