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 hard 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 tree root and bucket numbers | Bloomberg Coding Question

Quick Overview

This two-part question evaluates understanding of tree data representations and interval bucketing, testing competencies in identifying a tree root from parent–child adjacency records and in classifying numeric values into sorted-interval buckets; it falls within the data structures and algorithms domain (tree structures and array/interval processing). It is commonly used to assess reasoning about data invariants and edge-case handling — with the implicit assumptions that node ids are unique (no duplicates), inputs may be empty, boundaries may be negative, and values outside the outermost boundaries are treated as out of range — and it emphasizes a mix of conceptual understanding and practical algorithmic application.

Find tree root and bucket numbers

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given two independent tasks. ## Task 1: Find the root of a tree from adjacency logs You are given an unordered list of records describing a rooted tree. Each record is: - `node`: a node id (string or integer) - `children`: a list of node ids that are direct children of `node` All node ids are unique. Each node (except the root) appears as a child of exactly one other node. The root never appears as any node’s child. **Goal:** Return the id of the root node. **Input example:** - `[(1, [2, 3]), (2, [4]), (3, []), (4, [])]` **Output example:** - `1` ## Task 2: Bucket values between boundaries You are given: - A sorted array of numeric boundaries `B` of length `m` where `B[i] < B[i+1]` - An array of numeric values `A` Define buckets (intervals) between consecutive boundaries: - Bucket `i` corresponds to the interval `[B[i], B[i+1])` for `i = 0 .. m-2` Values `< B[0]` and `>= B[m-1]` are considered out of range. **Goal:** Classify values in `A` into these buckets and return an array `counts` of length `m-1`, where `counts[i]` is the number of values that fall into bucket `i`. **Example:** - `B = [0, 10, 20, 50]` - `A = [-1, 0, 3, 10, 19, 20, 49, 50]` Buckets: - `[0,10)`: values `{0,3}` → count 2 - `[10,20)`: values `{10,19}` → count 2 - `[20,50)`: values `{20,49}` → count 2 Output: - `[2, 2, 2]` State any assumptions you make about duplicates, empty inputs, and whether boundaries can be negative.

Quick Answer: This two-part question evaluates understanding of tree data representations and interval bucketing, testing competencies in identifying a tree root from parent–child adjacency records and in classifying numeric values into sorted-interval buckets; it falls within the data structures and algorithms domain (tree structures and array/interval processing). It is commonly used to assess reasoning about data invariants and edge-case handling — with the implicit assumptions that node ids are unique (no duplicates), inputs may be empty, boundaries may be negative, and values outside the outermost boundaries are treated as out of range — and it emphasizes a mix of conceptual understanding and practical algorithmic application.

Part 1: Find the Root of a Tree from Adjacency Logs

You are given an unordered list of records describing every node in a rooted tree. Each record is a tuple (node, children), where node is an integer id and children is a list of its direct children. Every node id is unique. Each non-root node appears in exactly one child list, and the root never appears in any child list. Return the id of the root node. Assumptions: official tests use valid trees with no duplicate node ids; records may appear in any order; empty child lists are allowed.

Constraints

Official tests assume 1 <= len(records) <= 10^5, though the reference solution safely returns None for an empty list.
Each node id is a unique integer.
The total number of child references across all records is len(records) - 1 for a valid tree.
Each non-root node appears in exactly one child list.

Examples

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

Expected Output: 1

Explanation: Nodes are {1,2,3,4}. Child nodes are {2,3,4}. The only node never seen as a child is 1.

Input: ([(5, []), (2, [5, 7]), (7, []), (9, [2]), (3, []), (1, [3, 9])],)

Expected Output: 1

Explanation: The records are unordered, but 1 is still the only node that never appears in any child list.

Input: ([(42, [])],)

Expected Output: 42

Explanation: Edge case: a single-node tree has that node as the root.

Input: ([(8, []), (3, [8, 10]), (10, []), (1, [3]), (6, []), (4, [6]), (2, [1, 4])],)

Expected Output: 2

Explanation: Every node except 2 appears somewhere as a child, so 2 is the root.

Hints

A root is the only node that never appears as anyone else's child.
Track all node ids and all child ids separately, then find the id that is in the first set but not the second.

Part 2: Bucket Values Between Boundaries

You are given a strictly increasing array of integer boundaries B and an array of integer values A. Bucket i represents the interval [B[i], B[i+1]) for i = 0 to len(B) - 2. A value smaller than B[0] or greater than or equal to B[len(B)-1] is out of range and should be ignored. Return an array counts of length len(B) - 1 where counts[i] is the number of values from A that fall into bucket i. Assumptions: duplicates in A are allowed and each occurrence is counted separately; boundaries may be negative; if fewer than 2 boundaries are provided, return an empty list.

Constraints

1 <= len(boundaries) <= 10^5
0 <= len(values) <= 2 * 10^5
boundaries[i] < boundaries[i+1] for all valid i
Both boundaries and values may be negative integers
Duplicates in values are allowed

Examples

Input: ([0, 10, 20, 50], [-1, 0, 3, 10, 19, 20, 49, 50])

Expected Output: [2, 2, 2]

Explanation: Values -1 and 50 are out of range. The remaining values fill buckets [0,10), [10,20), and [20,50) with counts 2, 2, and 2.

Input: ([-5, 0, 5], [-6, -5, -5, -1, 0, 4, 5])

Expected Output: [3, 2]

Explanation: Bucket [-5,0) gets -5, -5, -1. Bucket [0,5) gets 0 and 4. Values -6 and 5 are out of range.

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

Expected Output: [0, 0, 0]

Explanation: Edge case: with no values to classify, every bucket count is 0.

Input: ([10], [5, 10, 15])

Expected Output: []

Explanation: Edge case: fewer than two boundaries means there are no buckets.

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

Expected Output: [2]

Explanation: There is one bucket [0,1). Both 0 values are counted, while -1 and 1 are out of range.

Hints

For a value x, you need to know the last boundary that is less than or equal to x.
Because the boundaries are sorted, binary search can place each value into its bucket efficiently. Be careful that buckets are left-inclusive and right-exclusive.

Last updated: May 24, 2026

Loading coding console...

Quick Overview

Find tree root and bucket numbers

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Part 1: Find the Root of a Tree from Adjacency Logs

Constraints

Official tests assume 1 <= len(records) <= 10^5, though the reference solution safely returns None for an empty list.
Each node id is a unique integer.
The total number of child references across all records is len(records) - 1 for a valid tree.
Each non-root node appears in exactly one child list.

Examples

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

Expected Output: 1

Explanation: Nodes are {1,2,3,4}. Child nodes are {2,3,4}. The only node never seen as a child is 1.

Input: ([(5, []), (2, [5, 7]), (7, []), (9, [2]), (3, []), (1, [3, 9])],)

Expected Output: 1

Explanation: The records are unordered, but 1 is still the only node that never appears in any child list.

Input: ([(42, [])],)

Expected Output: 42

Explanation: Edge case: a single-node tree has that node as the root.

Input: ([(8, []), (3, [8, 10]), (10, []), (1, [3]), (6, []), (4, [6]), (2, [1, 4])],)

Expected Output: 2

Explanation: Every node except 2 appears somewhere as a child, so 2 is the root.

Hints

A root is the only node that never appears as anyone else's child.
Track all node ids and all child ids separately, then find the id that is in the first set but not the second.

Part 2: Bucket Values Between Boundaries

Constraints

1 <= len(boundaries) <= 10^5
0 <= len(values) <= 2 * 10^5
boundaries[i] < boundaries[i+1] for all valid i
Both boundaries and values may be negative integers
Duplicates in values are allowed

Examples

Input: ([0, 10, 20, 50], [-1, 0, 3, 10, 19, 20, 49, 50])

Expected Output: [2, 2, 2]

Explanation: Values -1 and 50 are out of range. The remaining values fill buckets [0,10), [10,20), and [20,50) with counts 2, 2, and 2.

Input: ([-5, 0, 5], [-6, -5, -5, -1, 0, 4, 5])

Expected Output: [3, 2]

Explanation: Bucket [-5,0) gets -5, -5, -1. Bucket [0,5) gets 0 and 4. Values -6 and 5 are out of range.

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

Expected Output: [0, 0, 0]

Explanation: Edge case: with no values to classify, every bucket count is 0.

Input: ([10], [5, 10, 15])

Expected Output: []

Explanation: Edge case: fewer than two boundaries means there are no buckets.

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

Expected Output: [2]

Explanation: There is one bucket [0,1). Both 0 values are counted, while -1 and 1 are out of range.

Hints

For a value x, you need to know the last boundary that is less than or equal to x.
Because the boundaries are sorted, binary search can place each value into its bucket efficiently. Be careful that buckets are left-inclusive and right-exclusive.

Last updated: May 24, 2026

Loading coding console...