Find tree root and bucket numbers

Q: Find tree root and bucket numbers

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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.

Find tree root and bucket numbers

Quick Overview

Task 1: Find the root of a tree from adjacency logs

Task 2: Bucket values between boundaries

Comments (0)