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 difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Patreon.

What role is this question designed for?

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

Design org chart lookup with preprocessing

Company: Patreon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given an organization chart represented as a list of pairs `[managerName, directReportName]`. Names are unique strings. The data may form a forest (multiple top-level managers) but contains no cycles. Implement an in-memory data structure that supports: 1) `lookUp(name)` → returns a tuple: - `role`: either `"mgr"` if the person has at least one direct report, otherwise `"ic"` - `directReportCount`: number of direct reports (out-degree) - `totalReportCount`: number of total reports in their subtree (all descendants) 2) Analyze the time and space complexity of your approach. 3) If there are a large number of `lookUp` requests, how would you optimize the system? 4) If `lookUp` must be **O(1)** time, what preprocessing would you do, and what would be the preprocessing cost? Follow-up: 5) Implement `add(managerName, reportName)` that adds a new reporting relationship (and creates missing nodes if needed). After adds, `lookUp` should reflect the updated org chart. Discuss/update complexity under your design. You should be able to run your own test cases to validate correctness.

Quick Answer: This question evaluates skills in data structures and algorithms, specifically tree/forest representation, aggregation of subtree metrics, dynamic updates, and rigorous time and space complexity analysis.

Part 1: Single org chart lookUp

You are given an organization chart represented as a list of (managerName, directReportName) pairs. The structure is a forest: there are no cycles, and each employee has at most one manager. Implement solution(edges, name) to return lookup information for exactly one person. Return a tuple (role, directReportCount, totalReportCount), where role is 'mgr' if the person has at least one direct report, otherwise 'ic'. Return None if the name does not exist in the chart.

Constraints

0 <= len(edges) <= 200000
Names are unique non-empty strings
The input graph is a forest: no cycles and each report has at most one manager
All known people appear in at least one pair

Examples

Input: ([('A', 'B'), ('A', 'C'), ('B', 'D')], 'A')

Expected Output: ('mgr', 2, 3)

Explanation: A directly manages B and C, and indirectly manages D.

Input: ([('A', 'B'), ('A', 'C'), ('B', 'D')], 'B')

Expected Output: ('mgr', 1, 1)

Explanation: B directly manages D and has one total descendant.

Input: ([('A', 'B'), ('A', 'C'), ('B', 'D')], 'C')

Expected Output: ('ic', 0, 0)

Explanation: C has no direct reports and no descendants.

Input: ([], 'X')

Expected Output: None

Explanation: Edge case: the org chart is empty.

Input: ([('A', 'B'), ('X', 'Y')], 'X')

Expected Output: ('mgr', 1, 1)

Explanation: The data can be a forest, so X is a separate top-level manager.

Hints

Build an adjacency list from manager to direct reports.
For a single query, you only need to traverse the queried person's subtree to count all descendants.

Part 2: Preprocess org chart for O(1) lookUps

You are given the same forest-shaped organization chart, but now there will be many lookup requests. Implement solution(edges, queries) so that you preprocess the org chart once, then answer each query in O(1) time. For each name in queries, return the tuple (role, directReportCount, totalReportCount), or None if the name does not exist.

Constraints

0 <= len(edges) <= 200000
0 <= len(queries) <= 200000
Names are unique non-empty strings
The input graph is a forest: no cycles and each report has at most one manager

Examples

Input: ([('A', 'B'), ('A', 'C'), ('B', 'D')], ['A', 'B', 'C', 'D'])

Expected Output: [('mgr', 2, 3), ('mgr', 1, 1), ('ic', 0, 0), ('ic', 0, 0)]

Explanation: All query answers are returned after one preprocessing pass.

Input: ([('CEO1', 'E1'), ('CEO2', 'E2'), ('CEO1', 'M1'), ('M1', 'I1')], ['CEO2', 'M1', 'ZZ'])

Expected Output: [('mgr', 1, 1), ('mgr', 1, 1), None]

Explanation: The chart is a forest, and unknown names should return None.

Input: ([], [])

Expected Output: []

Explanation: Edge case: no employees and no queries.

Input: ([], ['X'])

Expected Output: [None]

Explanation: Edge case: query on an empty chart.

Input: ([('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('E', 'F')], ['B', 'F', 'A'])

Expected Output: [('mgr', 2, 3), ('ic', 0, 0), ('mgr', 2, 5)]

Explanation: B has descendants D, E, and F. A has five total descendants.

Hints

If lookups are frequent, compute the answer for every known employee once and store it in a hash map.
A postorder traversal from each root lets you compute total descendant counts for all nodes.

Part 3: Org chart with add and live lookUps

You are given an initial organization chart as a forest of (managerName, directReportName) pairs. Then you must process operations of two kinds: ('add', managerName, reportName) and ('lookUp', name). Each add creates missing nodes if needed. After every add, later lookUp operations must reflect the updated org chart. Return the results of all lookUp operations in order. Return None for a lookUp on a name that does not exist. Assume every add is valid: it does not create a cycle, does not duplicate an existing edge, and does not give a report a second manager.

Constraints

0 <= len(initial_edges) <= 200000
0 <= len(operations) <= 200000
Names are unique non-empty strings
The initial chart is a forest: no cycles and each report has at most one manager
Each add operation is valid: no cycles, no duplicate edge, and report has no existing different manager

Examples

Input: ([('A', 'B'), ('A', 'C')], [('lookUp', 'A'), ('add', 'B', 'D'), ('lookUp', 'A'), ('lookUp', 'B'), ('lookUp', 'D')])

Expected Output: [('mgr', 2, 2), ('mgr', 2, 3), ('mgr', 1, 1), ('ic', 0, 0)]

Explanation: After adding D under B, A's total descendants increase from 2 to 3.

Input: ([], [('add', 'CEO', 'CTO'), ('lookUp', 'CEO'), ('lookUp', 'CTO')])

Expected Output: [('mgr', 1, 1), ('ic', 0, 0)]

Explanation: Edge case: start with an empty chart and create nodes through add.

Input: ([('A', 'B'), ('X', 'Y')], [('lookUp', 'Z'), ('add', 'Y', 'Q'), ('lookUp', 'X'), ('lookUp', 'Y')])

Expected Output: [None, ('mgr', 1, 2), ('mgr', 1, 1)]

Explanation: Unknown names return None, and updates only affect the relevant branch.

Input: ([('A', 'B'), ('B', 'C')], [('lookUp', 'A'), ('add', 'D', 'A'), ('lookUp', 'D'), ('lookUp', 'A'), ('lookUp', 'C')])

Expected Output: [('mgr', 1, 2), ('mgr', 1, 3), ('mgr', 1, 2), ('ic', 0, 0)]

Explanation: An existing root subtree can be attached under a new manager.

Input: ([('R', 'S'), ('T', 'U'), ('U', 'V')], [('add', 'S', 'T'), ('lookUp', 'R'), ('lookUp', 'S'), ('lookUp', 'T')])

Expected Output: [('mgr', 1, 4), ('mgr', 1, 3), ('mgr', 1, 2)]

Explanation: Adding an existing root subtree updates all ancestors above the insertion point.

Hints

Store parent pointers as well as children lists.
When adding a report under a manager, only that manager and its ancestors need their total descendant counts updated.

Quick Overview

This question evaluates skills in data structures and algorithms, specifically tree/forest representation, aggregation of subtree metrics, dynamic updates, and rigorous time and space complexity analysis.