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.

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.

Hints

  1. Build an adjacency list from manager to direct reports.
  2. 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.

Hints

  1. If lookups are frequent, compute the answer for every known employee once and store it in a hash map.
  2. 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.

Hints

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

Loading coding console...