How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Point72.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Point72 during technical interviews.

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

Quick Answer: 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

Solution

def circle_intersection_status(pairs: list[list[int]]) -> list[str]:
    result: list[str] = []
    for item in pairs:
        x1, y1, r1, x2, y2, r2 = item
        dx = x1 - x2
        dy = y1 - y2
        d2 = dx * dx + dy * dy
        # Special case: coincident circles
        if dx == 0 and dy == 0 and r1 == r2:
            result.append("INTERSECT")
            continue
        sr = r1 + r2
        sr2 = sr * sr
        dr = abs(r1 - r2)
        dr2 = dr * dr
        if d2 > sr2:
            result.append("SEPARATE")
        elif d2 == sr2:
            result.append("TOUCH")
        elif d2 < dr2:
            result.append("SEPARATE")
        elif d2 == dr2:
            result.append("TOUCH")
        else:
            result.append("INTERSECT")
    return result

Explanation

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).

Hints

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

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.