cswork / libraryOpen practice workspace

Coding questions · Point72

Classify relationships for multiple circle pairs

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.

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 Circle Pair Relationships

Hints

  1. Choose a representation that makes the core operation simple.
  2. Handle empty and boundary inputs before the main algorithm.