Classify relationships for multiple circle pairs

Q: Classify relationships for multiple circle pairs

This is a Coding & Algorithms interview question from Point72 for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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'].

Classify relationships for multiple circle pairs

Comments (0)