Determine Circle Intersection Status for Rendering Order
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
Graphics engine must evaluate multiple pairs of circles to decide rendering order based on intersection.
##### Question
Given an array where each element contains two circles defined as (x1, y1, r1, x2, y2, r
2), return for every pair whether they intersect, touch, or are separate.
##### Hints
Compute center distance d; compare d with r1+r2 and |r1−r2|.
Quick Answer: This question evaluates geometric reasoning and computational-geometry competency, including spatial relationship analysis and handling numerical edge cases relevant to pairwise object interaction.
You are given an array of circle pairs. Each pair is represented as [x1, y1, r1, x2, y2, r2], where (x1, y1) and r1 define the first circle and (x2, y2) and r2 define the second circle. For each pair, return one of: "INTERSECT" (two intersection points or coincident circles), "TOUCH" (tangent internally or externally), or "SEPARATE" (no common points, including one strictly inside the other). If the circles coincide (same center and radius), consider them "INTERSECT". Return a list of strings in the same order as the input pairs.
Constraints
- 1 <= len(pairs) <= 200000
- Coordinates and radii are integers: -1e9 <= x, y <= 1e9, 0 <= r <= 1e9
- Use integer arithmetic (compare squared distances) to avoid floating-point error
- Output list length must equal input list length
Solution
def circle_intersection_status(pairs: list[list[int]]) -> list[str]:
result: list[str] = []
for item in pairs:
x1, y1, r1, x2, y2, r2 = item
dx = x1 - x2
dy = y1 - y2
d2 = dx * dx + dy * dy
# Special case: coincident circles
if dx == 0 and dy == 0 and r1 == r2:
result.append("INTERSECT")
continue
sr = r1 + r2
sr2 = sr * sr
dr = abs(r1 - r2)
dr2 = dr * dr
if d2 > sr2:
result.append("SEPARATE")
elif d2 == sr2:
result.append("TOUCH")
elif d2 < dr2:
result.append("SEPARATE")
elif d2 == dr2:
result.append("TOUCH")
else:
result.append("INTERSECT")
return result
Explanation
Use squared distances to avoid floating-point operations: let d2 be the squared distance between centers. Compare d2 with (r1+r2)^2 and (|r1−r2|)^2. If d2 is greater than (r1+r2)^2, circles are disjoint externally. If d2 is less than (|r1−r2|)^2, one lies strictly inside the other without touching; both cases are SEPARATE. If d2 equals either boundary, they TOUCH (tangent). Otherwise, they INTERSECT at two points. If centers and radii match exactly, treat as INTERSECT (coincident).