Determine Reporting Relationships
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Technical Screen
Build an in-memory organization model that supports three operations on employee IDs:
1. `add_manager(a, b)`: employee `a` is the direct manager of employee `b`.
2. `add_peer(a, b)`: employees `a` and `b` share the same direct manager.
3. `is_manager(a, b)`: return whether employee `a` is a manager of employee `b`.
The answer should account for relationships that can be inferred from prior operations. For example, if `add_manager(m, x)` and `add_peer(x, y)` were previously recorded, then `is_manager(m, y)` should return `true`. You may assume the input is logically consistent and does not create invalid cycles in the org chart.
Explain how you would design the data structures and implement these operations efficiently.
Quick Answer: This question evaluates understanding of hierarchical relationship modeling, transitive inference across relations, and dynamic data-structure design for tracking manager and peer links.
Implement an in-memory organization model that processes operations on employee IDs in order. Each operation is a tuple `(op, a, b)` where:
- `("add_manager", a, b)`: employee `a` becomes the direct manager of employee `b`.
- `("add_peer", a, b)`: employees `a` and `b` share the same direct manager.
- `("is_manager", a, b)`: ask whether employee `a` is a direct or indirect manager of employee `b`.
Relationships can be inferred from earlier operations. For example, after `add_manager(m, x)` and `add_peer(x, y)`, `is_manager(m, y)` should be `True`.
Process the operations sequentially and return a list of answers for all `is_manager` queries, in order.
Notes:
- The input is logically consistent.
- No operation creates a cycle in the org chart.
- Repeating the same valid relationship is allowed.
- An employee is not considered their own manager.
Constraints
- 0 <= len(operations) <= 20000
- Employee IDs are integers in the range [-10^9, 10^9]
- At most 10000 distinct employee IDs appear
- The sequence of operations is logically consistent and does not create cycles
Examples
Input: ([("add_manager", 1, 2), ("add_peer", 2, 3), ("is_manager", 1, 3)])
Expected Output: [True]
Explanation: Employee 2 reports to 1. Since 2 and 3 are peers, 3 also reports to 1.
Input: ([("add_manager", 2, 4), ("is_manager", 1, 4), ("add_manager", 1, 2), ("is_manager", 1, 4), ("is_manager", 2, 4), ("is_manager", 4, 2)])
Expected Output: [False, True, True, False]
Explanation: Before 2 gets a manager, 1 is not a manager of 4. After adding 1 as manager of 2, 1 becomes an indirect manager of 4.