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.
Classify each circle pair using squared-distance comparisons to avoid floating point error.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
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))],)
Expected Output: ['TOUCHING_EXTERNALLY', 'IDENTICAL', 'CONCENTRIC', 'DISJOINT']
Explanation: Prompt example.
Input: ([((0,0,2),(4,0,2)), ((0,0,3),(2,0,1)), ((0,0,1),(5,0,1))],)
Expected Output: ['TOUCHING_EXTERNALLY', 'TOUCHING_INTERNALLY', 'DISJOINT']
Explanation: Touching and disjoint cases.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.