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

What role is this question designed for?

This question is commonly asked for Site Reliability Engineer candidates at Bytedance during technical interviews.

Find Maximum Chain Activations | Bytedance Coding Question

Find Maximum Chain Activations

Company: Bytedance

Role: Site Reliability Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` devices, where each device is represented as `[x, y, r]`. Device `i` is located at coordinates `(x, y)` and can directly activate device `j` if the Euclidean distance between them is less than or equal to `r_i`. Activation is directional: device `i` may be able to activate device `j` even when `j` cannot activate `i`. If you manually activate exactly one device first, every device reachable from it, directly or indirectly, will also become activated. Return the maximum number of devices that can be activated by choosing the best starting device. Also explain the time and space complexity of your approach.

Quick Answer: This question evaluates graph modeling and traversal skills combined with geometric distance computation and reachability analysis, requiring construction of a directed graph from coordinate-and-radius device data.

You are given a list of devices, where each device is represented as [x, y, r]. Device i is located at coordinates (x, y) and can directly activate device j if the Euclidean distance between them is less than or equal to the radius r of device i. Activation is directional, so device i may activate device j even if device j cannot activate device i. If you manually activate exactly one device first, then every device reachable from it, directly or indirectly, also becomes activated. Return the maximum number of devices that can be activated by choosing the best starting device. Count the starting device itself as activated. If the list is empty, return 0.

Constraints

0 <= n <= 100, where n is the number of devices
-10^5 <= x_i, y_i <= 10^5
0 <= r_i <= 10^5
All coordinates and radii are integers

Examples

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

Expected Output: 2

Explanation: Device 1 can activate device 0 because the distance is 4 and its radius is 4. Starting from device 1 activates both devices.

Input: ([[0, 0, 2], [2, 0, 2], [4, 0, 2], [10, 0, 1]],)

Expected Output: 3

Explanation: Starting from device 0 activates device 1, which then activates device 2. Device 3 is too far from all others.

Input: ([[5, 5, 1]],)

Expected Output: 1

Explanation: There is only one device, so the maximum activated count is 1.

Input: ([[0, 0, 5], [3, 4, 1], [5, 0, 5], [9, 0, 1]],)

Expected Output: 4

Explanation: Starting from device 0 activates devices 1 and 2. Device 2 can then activate device 3, so all 4 devices become active.

Input: ([],)

Expected Output: 0

Explanation: With no devices, nothing can be activated.

Input: ([[1, 1, 0], [1, 1, 0], [2, 2, 5]],)

Expected Output: 3

Explanation: Devices 0 and 1 share the same location, so they can activate each other even with radius 0. Device 2 can reach both of them, so starting from device 2 activates all 3 devices.

Hints

Model the devices as a directed graph: add an edge from i to j if device i can activate device j.
To test whether one device can activate another, compare squared distances instead of using square roots.

Quick Overview

This question evaluates graph modeling and traversal skills combined with geometric distance computation and reachability analysis, requiring construction of a directed graph from coordinate-and-radius device data.