Quick Overview

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

Overview: 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

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

Loading coding console...