How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Determine Reporting Relationships | Google Coding Question

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.

Input: ([("add_manager", 1, 2), ("add_peer", 2, 3), ("add_manager", 2, 4), ("is_manager", 3, 4), ("is_manager", 1, 4)])

Expected Output: [False, True]

Explanation: 2 and 3 are peers, so they share manager 1. But that does not make 3 a manager of 4. Employee 1 is an indirect manager of 4 through 2.

Input: ([("add_peer", 10, 11), ("is_manager", 5, 10), ("add_manager", 5, 11), ("is_manager", 5, 10), ("is_manager", 5, 11)])

Expected Output: [False, True, True]

Explanation: At first, 10 and 11 have no known manager. Once 11 is assigned manager 5, peer 10 also gets manager 5.

Input: ([("add_manager", -3, -1), ("add_peer", -1, -2), ("add_manager", -1, 4), ("is_manager", -3, -2), ("is_manager", -3, 4), ("is_manager", -1, 4)])

Expected Output: [True, True, True]

Explanation: Negative IDs work like any other IDs. -3 manages -1 and, through the peer relation, also manages -2. Since -1 manages 4, -3 is an indirect manager of 4.

Input: ([("is_manager", 7, 7)])

Expected Output: [False]

Explanation: An employee is not considered their own manager.

Input: ([])

Expected Output: []

Explanation: With no operations, there are no query results.

Hints

`add_peer(a, b)` means `a` and `b` share one direct manager, but they are not interchangeable as managers. Group such employees with Union-Find.
Once a peer group learns its direct manager, every current member of that group gets the same parent pointer. To answer `is_manager(a, b)`, walk upward from `b` through parent pointers.

Quick Overview

This question evaluates understanding of hierarchical relationship modeling, transitive inference across relations, and dynamic data-structure design for tracking manager and peer links.