Katkat

Find minimum activations to absorb all balls

UberSoftware Engineer · Online Assessment

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