Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE interview with a data structures design problem. The question was about modeling an org chart in memory with three operations, and the tricky part was handling inferred relationships correctly.

Questions Asked (1)

Design an in-memory org chart that supports three operations: marking one employee as the direct manager of another, marking two employees as peers (same manager), and querying whether one employee is a manager of another. The system must correctly handle inferred relationships. For example, if A manages X and X is a peer of Y, then A should also be recognized as a manager of Y.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The peer inference piece is what gets you.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the org chart as a graph where each employee is a node, and maintain explicit manager and peer relationships. Use union-find or graph traversal to infer transitive manager relationships, ensuring that peer groups are merged and manager links propagate correctly.

Pro tip: Clarify upfront whether peer relationships are symmetric and whether manager relationships are transitive, as these assumptions drastically affect the data structure and algorithm choice.

1. Clarify requirements and assumptions

Ask if peer relationships are symmetric, if manager relationships are transitive, and if cycles are possible. Confirm that inferred relationships should be computed on-the-fly or precomputed.

2. Choose data structures

Represent employees as nodes in a graph. Use a union-find (disjoint set) for peer groups and a directed graph (adjacency list) for manager relationships. Alternatively, use a single graph with labeled edges.

3. Design operations

For 'set manager', add a directed edge and propagate to all peers of the subordinate. For 'set peers', merge their peer groups and unify their manager sets. For 'is manager', perform a reachability query (DFS/BFS) from the potential manager to the subordinate.

4. Handle inference and updates

When adding a manager or peer, update all affected nodes to maintain consistency. Use union-find to efficiently merge peer groups and propagate manager relationships to all members.

5. Analyze trade-offs and complexity

Discuss time/space complexity: union-find gives near O(1) for peer merges, but manager queries may be O(V+E). Consider precomputing transitive closure for faster queries at the cost of update time.

Key Points to Mention

Graph representation: nodes as employees, edges as relationships (manager or peer).
Union-Find (Disjoint Set Union) for efficient peer group management and merging.
Transitive closure or reachability algorithms (DFS/BFS) for manager queries.
Propagation of manager relationships to all peers when a new manager is assigned.
Handling cycles and ensuring consistency (e.g., an employee cannot manage themselves).
Trade-offs between update time and query time (e.g., eager vs lazy inference).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.