How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Validate parent array forms a tree | Google Coding Question

Quick Overview

This question evaluates a candidate's understanding of tree and graph fundamentals, specifically parent-pointer representations, root identification, cycle detection, and connectivity invariants. Commonly asked in the Coding & Algorithms domain to assess reasoning about graph structure and invalid configurations, it requires both conceptual understanding and practical application.

Validate parent array forms a tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an integer array `parent` of length `n` describing a directed parent pointer for each node `i` (nodes are labeled `0..n-1`). - `parent[i]` is the parent of node `i`. - Exactly one node should be the root, indicated by `parent[root] = -1`. Determine whether these `n` nodes form a **valid rooted tree**. A valid rooted tree must satisfy all of the following: 1. **Exactly one root** (exactly one index `i` with `parent[i] = -1`). 2. **No cycles** (following parent pointers from any node must eventually reach the root). 3. **Connectivity** (every node is reachable from the root; equivalently, every node has exactly one simple path to the root). ## Input - `parent`: integer array of length `n` where each value is either `-1` or in `[0, n-1]`. ## Output - Return `true` if `parent` represents a valid rooted tree; otherwise return `false`. ## Notes / Edge Cases - `n` can be 1 (then the only valid tree is `parent[0] = -1`). - Self-parenting like `parent[i] = i` is invalid. - Multiple `-1` entries (multiple roots) is invalid. - A cycle among non-root nodes is invalid. - A disconnected component (some nodes not reachable from the root) is invalid.

Quick Answer: This question evaluates a candidate's understanding of tree and graph fundamentals, specifically parent-pointer representations, root identification, cycle detection, and connectivity invariants. Commonly asked in the Coding & Algorithms domain to assess reasoning about graph structure and invalid configurations, it requires both conceptual understanding and practical application.

You are given an integer array `parent` of length `n` describing a parent pointer for each node `i` where nodes are labeled `0` to `n-1`. - `parent[i]` is the parent of node `i`. - Exactly one node should be the root, indicated by `parent[root] = -1`. Determine whether these nodes form a valid rooted tree. A valid rooted tree must satisfy all of the following: 1. Exactly one root. 2. No cycles. 3. Every node belongs to the same connected structure and has a path to the root. Return `True` if `parent` represents a valid rooted tree; otherwise return `False`.

Constraints

1 <= n <= 2 * 10^5
Each `parent[i]` is either `-1` or an integer in `[0, n-1]`
`parent[i] = i` is invalid

Examples

Input: [-1, 0, 0, 1, 1]

Expected Output: True

Explanation: Node 0 is the only root. All other nodes are connected under it, and there are no cycles.

Loading coding console...

Quick Overview

Solution

Hints