Can you reach target with distance-threshold edges? | Google Coding Question

Quick Overview

This question evaluates understanding of graph connectivity and spatial proximity modeling, examining competencies in graph algorithms and computational geometry within the Coding & Algorithms domain relevant for Machine Learning Engineer roles.

Can you reach target with distance-threshold edges?

Company: Google

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a set of unordered 2D points `points[]`, a `start` point and an `end` point (both are included in `points`), and a function: ```text getDistance(p, q) ``` that returns the distance between two points `p` and `q`. Define an undirected graph where two points are connected by an edge **iff** `getDistance(p, q) < r` for a given threshold `r`. Task: Determine whether there exists a path from `start` to `end`. Follow-up: If `points` is very large and calling `getDistance` is expensive, how would you reduce repeated distance computations and/or avoid checking all pairs?

Quick Answer: This question evaluates understanding of graph connectivity and spatial proximity modeling, examining competencies in graph algorithms and computational geometry within the Coding & Algorithms domain relevant for Machine Learning Engineer roles.

Part 1: Reachability in a Distance-Threshold Point Graph

You are given a set of distinct 2D points, a start point, an end point, and a threshold r. Build an undirected graph where two points are connected by an edge if and only if their Euclidean distance is strictly less than r. Determine whether there exists any path from start to end, possibly using intermediate points.

Constraints

1 <= len(points) <= 2000
points contains distinct 2D points
-10^9 <= x, y <= 10^9
0 <= r <= 10^9
start and end are both present in points

Examples

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

Expected Output: True

Explanation: (0,0) connects to (1,0), and (1,0) connects to (2,0), so a path exists.

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

Expected Output: False

Explanation: The first three points form a chain, but (4,0) is too far from (2,0) to connect.

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

Expected Output: False

Explanation: The distance is exactly 5, but edges require distance strictly less than r.

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

Expected Output: True

Explanation: Start and end are the same point, so a path of length 0 exists.

Hints

Think of the points as nodes in an implicit graph. You do not need to store every edge ahead of time.
To test whether distance < r, compare squared distance with r * r and avoid calling sqrt.

Part 2: Scalable Reachability with Spatial Bucketing

You are given a very large set of distinct 2D integer points. Point i and point j are connected by an undirected edge if and only if their Euclidean distance is strictly less than r. You must determine whether start_index can reach end_index.\n\nA naive O(n^2) all-pairs check is too slow. The hidden tests are sparse: if you divide the plane into square buckets of side length r, each bucket contains only a small number of points. Use that fact to avoid checking all pairs.

Constraints

1 <= len(points) <= 200000
points contains distinct 2D integer points
-10^9 <= x, y <= 10^9
0 <= start_index, end_index < len(points)
1 <= r <= 10^9
Hidden tests guarantee that every square bucket of side length r contains at most 25 points

Examples

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

Expected Output: True

Explanation: Point 0 connects to 1, 1 connects to 2, and 2 connects to 3. So there is a path from index 0 to index 3.

Input: ([(0, 0), (3, 0), (6, 0)], 3, 0, 2)

Expected Output: False

Explanation: Distances between consecutive points are exactly 3, but edges require distance to be strictly less than 3, so no edges exist.

Input: ([(-5, -5), (-4, -4), (-3, -3), (-2, -2)], 2, 0, 3)

Expected Output: True

Explanation: Each consecutive pair is at distance sqrt(2), which is less than 2, so the chain reaches the last point.

Input: ([(10, -10)], 5, 0, 0)

Expected Output: True

Explanation: The start and end are the same point, so it is trivially reachable.

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

Expected Output: False

Explanation: Indices 0, 1, and 2 form a small connected component, but point 3 is too far from every other point.

Hints

If two points are closer than r, then their x-coordinates differ by less than r and their y-coordinates differ by less than r. That means they must lie in the same bucket or one of the 8 neighboring buckets.
Process points bucket by bucket and use Union-Find (Disjoint Set Union) so each candidate pair is checked at most once.

Last updated: May 21, 2026

Loading coding console...