Google NG Round1 Coding Recap: Validate Tree from Parent Array

The input is a parent-array representation of a graph, and the task is to decide whether it is a valid tree. The coding is simple, but interview clarity matters.

Problem Restatement

Given an array parent of length n:

• parent[i] is the parent of node i
• Root is represented by a special value (commonly -1)

Return whether this structure is a valid tree.

Interview-Ready Wording

I validate the structure with three checks:

1. Exactly one root
   Count how many indices satisfy parent[i] == -1. If it is not 1, return false.

2. Every node is visited at most once from the root
   Build an adjacency list from parent to children, then run DFS from the root.
   Use a visited array. If a node is reached again, the structure is invalid, return false.

3. Full coverage after DFS
   After traversal, if any node is still unvisited, it is disconnected, so return false.
   Only return true when all nodes are visited.

Complexity

• Time: O(n)
• Space: O(n) (adjacency + visited)

Common Mistakes

• Checking root count only, but not connectivity
• Missing repeated-visit detection in DFS
• Treating parent-array edges in a confusing direction
• Ignoring edge cases like single-node input

One-Line Takeaway

This problem is about stating the full tree criteria clearly: one root, no repeated path access, and all nodes reachable.

If you need interview support, feel free to reach out anytime.

#googlevo #vo #newgrad #sde #jobsearch #interviewprep

Further Reading (External Links)

• Google Careers
• Graph Valid Tree (LeetCode 261)
• Depth-First Search (Wikipedia)

Need real interview questions? Contact WeChat Coding0201: Get Questions.

Contact

Email: [email protected]
Telegram: @OAVOProxy