## Problem You are given a list of `(node_id, parent_id)` pairs representing a forest (collection of trees). A root node is one that does not appear as a child of any other node. Return all root node IDs in sorted order. ```python def find_root_ids(edges: list[tuple[int, int]]) -> list[int]: """edges: list of (node, parent). Return sorted list of roots.""" pass ``` ``` Input: edges = [(2,1), (3,1), (4,2), (5,3), (6,0)] Output: [1, 0] # Node 1 has no parent listed -> root # Node 0 has no parent listed -> root # Sorted: [0, 1] Input: edges = [(2,1), (3,2)] Output: [1] ``` ## Follow-ups 1. What if the input contains a cycle? How would you detect and report it? 2. How would you reconstruct the full tree structure (children mapping) from this edge list? 3. If `node_id` values are strings instead of integers, how does your solution change? 4. How would you find all leaf nodes in O(n) using the same edge list?

InterviewDB Experience

Root IDs: Find All Root Nodes in a Forest Given Parent Pointers

phone

Interview Experience

Problem You are given a list of (node_id, parent_id) pairs representing a forest (collection of trees). A root node is one that does not appear as a child of any other node. Return all root node IDs in sorted order. Follow-ups What if the input contains a cycle? How would you detect and report it? How would you reconstruct the full tree structure (children mapping) from this edge list? If node_id values are strings instead of integers, how does your solution change? How would you find all leaf n…

Full Details

🔒

Unlock all Ziphq questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a candidate experience report from a ziphq interview during the phone round.

It covers the following topics: Coding, Phone, Onsite, Strings .

Topics

Coding Phone Onsite Strings

Root IDs: Find All Root Nodes in a Forest Given Parent Pointers

Interview Experience

Full Details

About This Question

Topics

More Ziphq Interview Questions