Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round with a graph/relationship tracking problem. The core challenge was handling incremental data, where peer relationships get established before manager info is known, so you have to propagate backwards when new info arrives.

Questions Asked (1)

Design a system that processes a sequence of employee relationship operations: assigning a manager to an employee, declaring two employees as peers (same manager), and querying whether one employee manages another. The tricky part is that peer relationships can be established before a manager is known, so the system needs to handle incomplete and incrementally updated information.

Algorithms & Data StructuresSystem Design

Author's notes

The naive approach of just storing direct manager links breaks down fast once you introduce peers.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model employees as nodes in a graph where manager relationships form directed edges, and peer relationships form equivalence classes (disjoint sets) that may later merge when a manager is assigned. Use union-find to track peer groups and a separate structure (e.g., parent pointers or adjacency lists) for manager relationships, ensuring queries like 'does A manage B?' traverse the manager hierarchy. Handle incremental updates by lazily merging peer groups when a manager is assigned to one member.

Pro tip: Clarify upfront that 'manages' typically means direct or indirect reporting; if indirect, you'll need transitive closure or path compression. Also, discuss how to handle conflicts (e.g., assigning a manager to someone already in a peer group with a different manager) to show robustness.

1. Clarify requirements and assumptions

Ask whether 'manages' means direct or indirect, whether peer groups are transitive, and if operations are online or batched. Confirm constraints like number of employees and operation frequency.

2. Choose data structures

Use union-find (disjoint set) to represent peer groups, with each set tracking a designated manager (if known). Use a separate map or tree to represent manager-to-employee relationships for hierarchy queries.

3. Design operations

For assign_manager(emp, mgr): set emp's manager, and if emp is in a peer group, propagate the manager to all peers (or mark the group's manager). For declare_peers(a, b): union their peer groups, merging manager info if present. For is_manager(a, b): check if b is in a's subtree in the manager hierarchy.

4. Handle incomplete information

When peers are declared before a manager is known, store the peer group without a manager. When a manager is later assigned to any member, update the group's manager and ensure all members reflect that manager.

5. Analyze complexity and edge cases

Discuss time complexity: union-find operations near O(1) amortized, manager queries O(depth) or O(1) with path compression. Address conflicts (e.g., assigning conflicting managers to peers) and how to resolve them.

Key Points to Mention

Union-Find (Disjoint Set Union) for peer groups with path compression and union by rank
Separate representation for manager hierarchy (e.g., parent pointers or adjacency list)
Lazy propagation of manager assignment to peer group members
Handling conflicts when peers have different managers (e.g., error or override)
Time complexity analysis: near O(1) for peer operations, O(depth) for manager queries
Scalability considerations for large numbers of employees and operations

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