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
Hints
- Compare squared center distance d2 with (r1+r2)^2 and (|r1−r2|)^2.
- If d2 > (r1+r2)^2 or d2 < (|r1−r2|)^2, circles are SEPARATE.
- If d2 equals one of those squared values, circles TOUCH.
- If centers and radii are identical, treat as INTERSECT.