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 Waymo.

What role is this question designed for?

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

Validate a Parent-Child Forest | Waymo Coding Question

Quick Overview

This question evaluates understanding of graph theory concepts—specifically rooted trees, parent-child relationships, cycle detection, and node in-degree constraints—and the ability to implement validation logic for data structures representing forests.

Validate a Parent-Child Forest

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of directed edges, where each edge is represented as `(parent, child)`. The edges describe parent-child relationships among nodes in a graph. Determine whether the graph is a valid forest. A valid forest is a collection of zero or more rooted trees, where: - A node may have any number of children. - Each node may have at most one parent. - There must be no directed or undirected cycles. - Multiple root nodes are allowed. - Nodes may appear only as parents, only as children, or both. Implement a function that returns whether the given list of edges forms a valid forest. Also design meaningful test cases, including edge cases such as an empty edge list, multiple disconnected trees, a node with two parents, and cycles.

Quick Answer: This question evaluates understanding of graph theory concepts—specifically rooted trees, parent-child relationships, cycle detection, and node in-degree constraints—and the ability to implement validation logic for data structures representing forests.

You are given a list of directed edges, where each edge is represented as (parent, child). The edges describe parent-child relationships among nodes identified by integers. Determine whether these edges form a valid forest. A valid forest is a collection of zero or more rooted trees, where: - A node may have any number of children. - Each node may have at most one parent. - There must be no directed or undirected cycles. - Multiple root nodes are allowed. - Nodes may appear only as parents, only as children, or both. Return True if the given edges form a valid forest, otherwise return False. Notes: - An empty edge list is a valid forest. - A self-loop like (x, x) is invalid because it creates a cycle.

Constraints

0 <= len(edges) <= 200000
-10^9 <= parent, child <= 10^9
Each edge is a pair of integers

Examples

Input: []

Expected Output: True

Explanation: No edges means there are no cycles and no node has multiple parents, so the empty graph is a valid forest.

Input: [(1, 2)]

Expected Output: True

Explanation: A single parent-child relationship forms a valid tree.

Input: [(1, 2), (1, 3), (4, 5)]

Expected Output: True

Explanation: This forms two disconnected trees: one rooted at 1 and one rooted at 4.

Input: [(-1, -2), (-2, -3), (10, 11)]

Expected Output: True

Explanation: Negative labels are allowed. These edges form two separate acyclic trees.

Input: [(1, 3), (2, 3)]

Expected Output: False

Explanation: Node 3 has two different parents, which is not allowed in a forest.

Input: [(1, 2), (2, 3), (3, 1)]

Expected Output: False

Explanation: These edges create a cycle, so the graph is not a forest.

Input: [(7, 7)]

Expected Output: False

Explanation: A self-loop is a cycle, so it cannot appear in a valid forest.

Hints

Track the parent assigned to each child. If a child is assigned more than once, the structure cannot be a forest.
If you ignore edge direction, every tree in a forest is acyclic. A Union-Find (Disjoint Set Union) structure can detect cycles efficiently while processing edges.

Quick Overview