Katkat
Back

Design org chart lookup with preprocessing

PatreonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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)

  1. Analyze the time and space complexity of your approach.

  2. If there are a large number of lookUp requests, how would you optimize the system?

  3. If lookUp must be O(1) time, what preprocessing would you do, and what would be the preprocessing cost?

Follow-up:

  1. 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.