Google·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Google SWE interview with a tree design problem that started simple and got complicated fast. The follow-ups kept stacking and I wasn't fully prepared for how deep they'd go on deletion edge cases.

Questions Asked (2)

Design an employee hierarchy class that supports adding an employee under a given manager and deleting an employee by ID. How do you handle deleting a manager, deleting the root/CEO, and preventing cycles in the hierarchy?

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with a basic map from id to node and got addEmployee working pretty quickly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and defining the data structures (e.g., a map from ID to Employee and a tree structure). Then walk through the core operations (add, delete) and edge cases (deleting a manager, root, cycle prevention), discussing trade-offs and possible solutions. Conclude by summarizing the design and its complexity.

Pro tip: Explicitly discuss the trade-offs between different deletion strategies (e.g., reassigning children vs. cascading delete) and how they affect data integrity and performance. Also, mention that cycle prevention can be enforced by checking ancestry before adding a new relationship.

1. Clarify Requirements and Assumptions

Ask questions to understand constraints: Can an employee have multiple managers? Should deletion be soft or hard? What are the expected operation frequencies? This shows you think before coding.

2. Design Data Structures

Propose using a hash map for O(1) employee lookup by ID and a tree structure (e.g., each employee has a list of direct reports) for hierarchy. Mention that a parent pointer can help with cycle detection.

3. Implement Core Operations

Describe addEmployee(managerId, employee) and deleteEmployee(employeeId). For add, ensure no cycle by checking if the new manager is a descendant of the employee. For delete, handle different cases.

4. Handle Edge Cases

Discuss deleting a manager (reassign reports to the manager's manager or cascade delete), deleting the root/CEO (disallow or promote a successor), and preventing cycles (ancestry check).

5. Analyze Trade-offs and Complexity

Compare strategies: reassigning vs. cascading delete in terms of data loss and performance. State time/space complexity for each operation and discuss scalability.

Key Points to Mention

Use a hash map (ID -> Employee) for O(1) lookup and a tree structure for hierarchy.
Cycle prevention: before adding, check if the new manager is a descendant of the employee (using parent pointers or DFS).
Deleting a manager: options include reassigning direct reports to the manager's manager or cascading delete; discuss trade-offs.
Deleting the root/CEO: either disallow, or promote a successor (e.g., most senior report) and reassign others.
Time complexity: add O(1) average with cycle check O(depth), delete O(1) for lookup plus O(k) for reassignment where k is number of reports.
Consider soft deletion (mark as inactive) to preserve historical data and avoid breaking references.

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

Follow-up: each employee has a seniority level. When deleting a manager, how do you pick which employee in that manager's subtree gets promoted as the replacement? What if there's a tie in seniority?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I started losing ground.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the data structure and constraints: the hierarchy is a tree, and we need to find the most senior employee in the subtree rooted at the manager being deleted. Then, define a deterministic tie-breaking rule, such as smallest employee ID or alphabetical order, and discuss how to implement the search efficiently, possibly with a precomputed data structure.

Pro tip: Mention that in a real system, you'd likely maintain a priority queue or sorted structure per subtree to avoid O(n) searches, and that tie-breaking should be consistent and documented to avoid ambiguity.

1. Clarify the problem and constraints

Ask whether the tree is static or dynamic, and whether we need to support frequent deletions. Clarify what 'seniority level' means (e.g., numeric value) and whether ties are possible.

2. Define the selection criteria

State that we want the employee with the highest seniority level in the subtree. If multiple have the same level, apply a deterministic tie-breaker like smallest employee ID or earliest hire date.

3. Choose an efficient algorithm

For a single query, a DFS/BFS traversal of the subtree works. For frequent queries, precompute for each node the best candidate in its subtree using a post-order traversal, or use a segment tree/heap per subtree.

4. Handle tie-breaking

When seniority levels are equal, compare secondary keys (e.g., employee ID). Ensure the tie-breaker is consistent and explain how it integrates into the comparison logic.

5. Discuss trade-offs and extensions

Mention time/space trade-offs: O(n) per query vs O(n) preprocessing and O(1) query. Also consider if the tree changes dynamically, requiring updates to precomputed data.

Key Points to Mention

Tree traversal (DFS/BFS) to explore the subtree
Priority queue or heap to efficiently find max seniority
Tie-breaking rule (e.g., smallest ID) for determinism
Precomputation for frequent queries (e.g., post-order traversal storing best candidate)
Time and space complexity trade-offs
Handling dynamic updates if the tree changes

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