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 Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Find minimum activations to absorb all balls

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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.

Quick Answer: 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. Ball i is located at coordinates (x[i], y[i]). You are also given a distance threshold d. Two balls attract each other if the Euclidean distance between them is strictly less than d. Attraction is transitive: if ball A attracts B, and B attracts C, then activating A will eventually absorb all three balls. Time proceeds in discrete steps. In one step, you may choose exactly one ball that has not yet been absorbed. That activation absorbs every ball in the same attraction chain as the chosen ball. Return the minimum number of steps required to absorb all balls. Important: attraction is determined from the original coordinates only, so this is a static connectivity problem.

Constraints

0 <= n <= 2000
len(x) = len(y) = n
-10^9 <= x[i], y[i] <= 10^9
0 <= d <= 10^9
Two balls are connected only if their Euclidean distance is strictly less than d

Examples

Input: (6, [0, 1, 10, 11, 50, 51], [0, 0, 0, 0, 0, 0], 2.0)

Expected Output: 3

Explanation: Balls (0,1), (10,11), and (50,51) each form separate attraction groups, so one activation is needed for each group.

Input: (3, [0, 1, 2], [0, 0, 0], 1.5)

Expected Output: 1

Explanation: Ball 0 attracts 1, and 1 attracts 2. Even though 0 and 2 are not directly connected, all three are in one chain, so one activation is enough.

Input: (2, [0, 3], [0, 4], 5.0)

Expected Output: 2

Explanation: The distance is exactly 5, but attraction requires the distance to be strictly less than d, so these balls are not connected.

Input: (3, [1, 1, 2], [1, 1, 2], 0.0)

Expected Output: 3

Explanation: With d = 0, even balls at the same coordinates do not attract because 0 is not strictly less than 0. Each ball must be activated separately.

Input: (0, [], [], 10.0)

Expected Output: 0

Explanation: There are no balls to absorb, so zero activations are required.

Hints

Model each ball as a node in an undirected graph, and connect two nodes if their distance is less than d.
Each activation absorbs exactly one connected component, so the answer is the number of connected components.

Quick Overview

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.