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.