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

Intermediate

Jul 2026

Summary

Google SWE coding round, one problem the whole time. Tree validation, which sounds straightforward until you're actually in the room trying to remember every edge case you've ever seen.

Questions Asked (1)

Given an integer array where each element represents the parent of that index's node (with -1 marking the root), determine whether the array describes a valid rooted tree.

Algorithms & Data Structures

Author's notes

I jumped straight to cycle detection and forgot to check for multiple roots first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Approach this problem by identifying the necessary and sufficient conditions for a valid rooted tree: exactly one root (one -1), no cycles, and all nodes connected (i.e., the graph is fully connected). Use either Union-Find or DFS/BFS to detect cycles and verify connectivity, while simultaneously validating structural constraints like a single root and each node having at most one parent.

Pro tip: Mention edge cases upfront — such as an empty array, multiple roots, self-loops (parent[i] == i), or nodes pointing to out-of-range indices — as Google interviewers specifically look for candidates who think defensively and don't just solve the happy path.

1. Clarify Constraints & Edge Cases

Confirm input assumptions: can the array be empty, can indices be out of bounds, and is exactly one -1 guaranteed? Explicitly state the edge cases you plan to handle, such as multiple roots, self-loops, or disconnected components.

2. Define Valid Tree Conditions

Articulate that a valid rooted tree requires: (1) exactly one node with parent -1, (2) no cycles, and (3) all n nodes are connected forming a single component. This gives your solution a clear checklist to verify.

3. Choose & Explain Your Algorithm

Select Union-Find for O(n α(n)) efficiency or DFS/BFS for clarity, and justify your choice. For Union-Find, union each node with its parent and detect a cycle if they already share the same root; for DFS, track visited and in-recursion-stack states.

4. Implement & Validate

Code the solution while narrating your logic — count roots as you scan, apply your cycle-detection strategy, and after processing all edges verify that the number of connected components equals exactly one.

5. Analyze Complexity & Test

State time complexity O(n) or O(n α(n)) and space complexity O(n), then walk through 2-3 test cases: a valid tree, a graph with a cycle, and a disconnected forest to confirm correctness.

Key Points to Mention

Exactly one root condition: the array must contain precisely one -1 value
Cycle detection using Union-Find (with path compression and union by rank) or DFS with a visited/in-stack marker
Connectivity check: after processing all parent-child edges, confirm there is exactly one connected component
Each node has at most one parent by the array's structure, but you should still guard against self-loops (parent[i] == i) and out-of-range parent values
Trade-offs between Union-Find (optimal time complexity) vs. DFS/BFS (more intuitive and easier to explain)
The equivalence between a valid rooted tree and a graph with n nodes, n-1 edges, no cycles, and full connectivity

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