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