Find minimum activations to absorb all balls
UberSoftware Engineer · Online AssessmentLast updated
This question evaluates the ability to model Euclidean-distance relations as a static connectivity graph and reason about the minimum number of activations needed to absorb all nodes, testing computational geometry and graph algorithms competency.
You are given n balls on a 2D plane, where ball i is at coordinate ((x_i, y_i)). You are also given a distance threshold d.
Two balls are considered to attract each other if their Euclidean distance is strictly less than (d). Attraction is transitive via a chain reaction: if ball A attracts B, and B attracts C, then starting from A will eventually cause A, B, and C to be absorbed into the same cluster.
Time proceeds in discrete steps. In each time step, you may choose one not-yet-absorbed ball to start the attraction process. In that step, all balls that are connected to it via a chain of attractions become absorbed.
Return the minimum number of time steps required so that all balls are absorbed.
Input:
- Integer (n)
- Arrays (x[1..n], y[1..n])
- Real number (d)
Output:
- An integer: the minimum number of time steps.
Clarifications/Notes:
- Use Euclidean distance (\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}).
- The attraction relation is determined from the original coordinates (i.e., treat it as a static graph connectivity problem).
Example (illustrative): If the balls form 3 disconnected attraction groups, the answer is 3 because you must start the process once in each group.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.