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.

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.

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.

Read the full Bloomberg Software Engineer interview experience this question came from

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.

Hints

  1. 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.
  2. Build a set of every child id seen across all records, then scan all known ids for the one missing from that child set.
  3. 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.

Loading coding console...