Interview Experience
Problem
You are given a list of 2D integer coordinates. Group them into clusters such that all points within a cluster are within Euclidean distance r of at least one other point in the same cluster.
Return each cluster as a sorted list of point indices, with clusters sorted by their smallest index.
python
def group_coordinates(
points: list[tuple[int, int]],
r: float
) -> list[list[int]]:
pass
**Input**:
points = [(0,0),(1,1),(10,10),(11,11),(0,1)]
r = 2.0
Output: [[0,1,4], [2,3]]
# (0,0),(1,1),(0,1) are all within r=2 of each other -> cluster
# (10,10),(11,11) -> cluster
**Input**:
points = [(0,0),(100,100)]
r = 1.0
Output: [[0],[1]]
Follow-ups
- This is essentially finding connected components in a graph where edges connect points within distance
r. What graph traversal do you use? - The naive approach is O(n^2) for edge construction. How does a k-d tree reduce this?
- How does this compare to DBSCAN clustering? What is the role of
rvs DBSCAN's epsilon? - Extend to 3D coordinates — what changes in your approach?
Full Details
Problem
You are given a list of 2D integer coordinates. Group them into clusters such that all points within a cluster are within Euclidean distance r of at least one other point in the same cluster.
Return each cluster as a sorted list of point indices, with clusters sorted by their smallest index.
python
def group_coordinates(
points: list[tuple[int, int]],
r: float
) -> list[list[int]]:
pass
**Input**:
points = [(0,0),(1,1),(10,10),(11,11),(0,1)]
r = 2.0
Output: [[0,1,4], [2,3]]
# (0,0),(1,1),(0,1) are all within r=2 of each other -> cluster
# (10,10),(11,11) -> cluster
**Input**:
points = [(0,0),(100,100)]
r = 1.0
Output: [[0],[1]]
Follow-ups
- This is essentially finding connected components in a graph where edges connect points within distance
r. What graph traversal do you use? - The naive approach is O(n^2) for edge construction. How does a k-d tree reduce this?
- How does this compare to DBSCAN clustering? What is the role of
rvs DBSCAN's epsilon? - Extend to 3D coordinates — what changes in your approach?
About This Question
This is a candidate experience report from a applied intuition interview during the phone round.
It covers the following topics: Coding, Graph, Phone, Onsite .