Quick Overview

This question evaluates geometric reasoning and computational-geometry competency, including spatial relationship analysis and handling numerical edge cases relevant to pairwise object interaction.

Determine Circle Intersection Status for Rendering Order

Company: Point72

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Scenario Graphics engine must evaluate multiple pairs of circles to decide rendering order based on intersection. ##### Question Given an array where each element contains two circles defined as (x1, y1, r1, x2, y2, r 2), return for every pair whether they intersect, touch, or are separate. ##### Hints Compute center distance d; compare d with r1+r2 and |r1−r2|.

Overview: This question evaluates geometric reasoning and computational-geometry competency, including spatial relationship analysis and handling numerical edge cases relevant to pairwise object interaction.

You are given an array of circle pairs. Each pair is represented as [x1, y1, r1, x2, y2, r2], where (x1, y1) and r1 define the first circle and (x2, y2) and r2 define the second circle. For each pair, return one of: "INTERSECT" (two intersection points or coincident circles), "TOUCH" (tangent internally or externally), or "SEPARATE" (no common points, including one strictly inside the other). If the circles coincide (same center and radius), consider them "INTERSECT". Return a list of strings in the same order as the input pairs.

Constraints

  • 1 <= len(pairs) <= 200000
  • Coordinates and radii are integers: -1e9 <= x, y <= 1e9, 0 <= r <= 1e9
  • Use integer arithmetic (compare squared distances) to avoid floating-point error
  • Output list length must equal input list length

Hints

  1. Compare squared center distance d2 with (r1+r2)^2 and (|r1−r2|)^2.
  2. If d2 > (r1+r2)^2 or d2 < (|r1−r2|)^2, circles are SEPARATE.
  3. If d2 equals one of those squared values, circles TOUCH.
  4. If centers and radii are identical, treat as INTERSECT.

Loading coding console...

Show the approach

Approach

Use squared distances to avoid floating-point operations: let d2 be the squared distance between centers. Compare d2 with (r1+r2)^2 and (|r1−r2|)^2. If d2 is greater than (r1+r2)^2, circles are disjoint externally. If d2 is less than (|r1−r2|)^2, one lies strictly inside the other without touching; both cases are SEPARATE. If d2 equals either boundary, they TOUCH (tangent). Otherwise, they INTERSECT at two points. If centers and radii match exactly, treat as INTERSECT (coincident).

Time complexity:
O(n)
Space complexity:
O(1) extra (excluding output)