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

What role is this question designed for?

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

Find root from child adjacency lists | Bloomberg Coding Question

Find root from child adjacency lists

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You're given an unordered list describing a rooted n-ary tree. Each item is a record of the form {id: int, children: set<int>} listing a node's direct children; parent links are not provided. All node ids are unique, and every non-root node appears exactly once in some children set. Find and return the root node id. Describe the algorithm, data structures used, time and space complexity, and how you would detect/handle invalid inputs such as multiple roots, cycles, or missing references.

Quick Answer: This question evaluates understanding of tree data structures, set-based membership reasoning, and algorithmic analysis including time and space complexity and robustness to invalid inputs such as multiple roots or cycles.

You're given an unordered list describing a rooted n-ary tree. Each record has a node id and the set of that node's direct children; parent links are NOT provided. All node ids are unique, and every non-root node appears exactly once in some children set. Return the root node id — the single node that never appears as anyone's child. The input is passed as a list of records, where each record is a pair `[id, [child_id, ...]]`. Nodes that appear only as children (and have no record of their own) are still valid tree nodes. Invalid input handling: if the structure does not have exactly one root — e.g. multiple disconnected roots (a forest), or a cycle where every node is some other node's child so no root exists — return -1. Example: records = [[1, [2, 3]], [2, [4, 5]], [3, []], [4, []], [5, []]] Node 1 never appears in any children set, so the root is 1.

Constraints

All node ids are unique.
Every non-root node appears exactly once across all children sets.
A node may appear only as a child (with no record of its own) and is still a valid leaf.
Return -1 if there is not exactly one root (multiple roots / forest, or a cycle leaving no root).

Examples

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

Expected Output: 1

Explanation: Nodes 2,3,4,5 all appear in some children set; only 1 never does, so 1 is the root.

Input: [[10, [20]], [20, [30]], [30, []]]

Expected Output: 10

Explanation: Linear chain 10 -> 20 -> 30; 10 is never a child, so it is the root.

Input: [[7, []]]

Expected Output: 7

Explanation: Single node with no children is its own root.

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

Expected Output: 5

Explanation: Wide star: 5 has four children and is never a child itself.

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

Expected Output: -1

Explanation: Cycle 1 -> 2 -> 3 -> 1: every node is some node's child, so there is no root; return -1.

Input: [[1, [2]], [3, [4]]]

Expected Output: -1

Explanation: Two disjoint trees (a forest): both 1 and 3 are roots, so the input is invalid; return -1.

Input: [[100, [50, 60]], [50, [25]], [60, []], [25, []]]

Expected Output: 100

Explanation: Root 100 has children 50 and 60; 50 in turn has child 25. Only 100 is never a child.

Hints

The root is the only node that is never listed as a child of anything. Collect the set of all ids and the set of all child ids — the root is in the first but not the second.
Build a set of every child id seen across all records, then scan all known ids for the one missing from that child set.
For invalid-input detection, count how many ids are never anyone's child: exactly one means a valid root; zero (a full cycle) or more than one (a forest) means the input is malformed.

Quick Overview

This question evaluates understanding of tree data structures, set-based membership reasoning, and algorithmic analysis including time and space complexity and robustness to invalid inputs such as multiple roots or cycles.