Classify relationships for multiple circle pairs
Circle Pair Relationship Classifier
Given an array of N circle pairs, where each circle is defined by its (x, y) integer coordinates and a non-negative integer radius r, your task is to classify the relationship for each pair.
Input
An array pairs containing N circle pairs. Each circle is represented as (x, y, r).
Output
An array of strings, where each string is the classification label for the corresponding circle pair in the input order.
Classification Categories
For two circles with centers (x1, y1), (x2, y2) and radii r1, r2, let d be the distance between their centers. The classifications are:
- IDENTICAL: Same center and same radius.
- CONCENTRIC: Same center, but different radii.
- TOUCHING_EXTERNALLY: The distance between centers
dis exactly equal tor1 + r2. - TOUCHING_INTERNALLY: The distance between centers
dis exactly equal to|r1 − r2|, andr1 ≠ r2. - INTERSECTING: The distance
dsatisfies|r1 − r2| < d < r1 + r2. - DISJOINT: The distance
dis greater thanr1 + r2.
Constraints and Requirements
Ncan be up to2 * 10^5.- Coordinates (
x,y) and radii (r) can be up to10^9. - All coordinates and radii are integers. Radii
rare non-negative. - Precision: To avoid floating-point errors, calculations involving distances should use 64-bit integers and compare squared distances.
- Degenerate Cases: Handle
r=0(circles become points), zero-distance centers, and any potential negative inputs (which should be rejected as invalid). - Complexity: Provide the time and space complexity of your solution.
- Testing: Explain how you would test boundary cases for your implementation.
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))]
Output:
['INTERSECTING','IDENTICAL','CONCENTRIC','DISJOINT']
AI interview prep
Core dilemma
Balancing computational efficiency and absolute precision for geometric comparisons, while robustly handling all specified edge and degenerate cases for circle relationships.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Classify relationships for multiple circle pairs
Circle Pair Relationship Classifier
Given an array of N circle pairs, where each circle is defined by its (x, y) integer coordinates and a non-negative integer radius r, your task is to classify the relationship for each pair.
Input
An array pairs containing N circle pairs. Each circle is represented as (x, y, r).
Output
An array of strings, where each string is the classification label for the corresponding circle pair in the input order.
Classification Categories
For two circles with centers (x1, y1), (x2, y2) and radii r1, r2, let d be the distance between their centers. The classifications are:
- IDENTICAL: Same center and same radius.
- CONCENTRIC: Same center, but different radii.
- TOUCHING_EXTERNALLY: The distance between centers
dis exactly equal tor1 + r2. - TOUCHING_INTERNALLY: The distance between centers
dis exactly equal to|r1 − r2|, andr1 ≠ r2. - INTERSECTING: The distance
dsatisfies|r1 − r2| < d < r1 + r2. - DISJOINT: The distance
dis greater thanr1 + r2.
Constraints and Requirements
Ncan be up to2 * 10^5.- Coordinates (
x,y) and radii (r) can be up to10^9. - All coordinates and radii are integers. Radii
rare non-negative. - Precision: To avoid floating-point errors, calculations involving distances should use 64-bit integers and compare squared distances.
- Degenerate Cases: Handle
r=0(circles become points), zero-distance centers, and any potential negative inputs (which should be rejected as invalid). - Complexity: Provide the time and space complexity of your solution.
- Testing: Explain how you would test boundary cases for your implementation.
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))]
Output:
['INTERSECTING','IDENTICAL','CONCENTRIC','DISJOINT']