Classify relationships for multiple circle pairs
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an array pairs of N circle pairs, where each circle is (x, y, r) with integer coordinates and r ≥ 0, classify each pair into one of: IDENTICAL (same center and radius), CONCENTRIC (same center, different radii), TOUCHING_EXTERNALLY (distance between centers = r1 + r2), TOUCHING_INTERNALLY (distance between centers = |r1 − r2|, r1 ≠ r2), INTERSECTING (|r1 − r2| < d < r1 + r2), or DISJOINT (d > r1 + r2). Return an array of these labels in order.
Constraints:
- N up to 2e5; coordinates and radii up to 1e9.
- Use 64-bit integers and compare using squared distances to avoid floating-point error.
- Treat degenerate cases carefully: r=0 (points), zero-distance centers, negative inputs should be rejected.
- Provide the time and space complexity, and explain how you'd test boundary cases.
- Example input: [((0,0,2),(3,0,1)), ((0,0,1),(0,0,1)), ((0,0,3),(0,0,1)), ((0,0,2),(5,0,2))] should output ['INTERSECTING','IDENTICAL','CONCENTRIC','DISJOINT'].
Quick Answer: This question evaluates computational geometry skills, careful integer arithmetic for numeric precision, case-based classification logic, and analysis of time and space complexity in the Coding & Algorithms domain for Data Scientist roles.