Queries on Number of Points Inside a Circle

Queries on Number of Points Inside a Circle

What is this problem about?

The Queries on Number of Points Inside a Circle problem gives you a list of 2D points and a list of circle queries (center, radius). For each query, count how many points lie inside or on the circle boundary. This easy-to-medium coding problem tests basic geometric distance comparison. The array, math, and geometry interview pattern is demonstrated.

Why is this asked in interviews?

Google asks this to test geometric intuition — specifically using the squared distance formula to avoid floating-point square roots. For small inputs, O(n × q) brute force is acceptable.

Algorithmic pattern used

Brute force with squared distance. For each query (cx, cy, r): count points (px, py) where (px-cx)² + (py-cy)² ≤ r². Using squared distance avoids sqrt computation, keeping comparisons exact integer arithmetic.

Example explanation

points=[(1,3),(3,3),(5,3),(2,2)], queries=[(2,3,1),(4,3,1),(1,1,2)].

• Query (2,3,1): r²=1. Check: (1,3)→1≤1✓, (3,3)→1≤1✓, (5,3)→9✗, (2,2)→1≤1✓. Count=3.
• Query (4,3,1): r²=1. (3,3)→1✓, (5,3)→1✓. Count=2.
• Query (1,1,2): r²=4. (1,3)→4✓, (2,2)→2≤4✓. Count=2.

Common mistakes candidates make

• Using sqrt((px-cx)² + (py-cy)²) ≤ r with float precision issues.
• Forgetting the ≤ (points on boundary are included).
• Integer overflow for large coordinates (use long).
• O(n × q) without knowing it's acceptable for given constraints.

Interview preparation tip

Geometric distance problems almost always use squared distance to avoid floating-point issues. The condition dx² + dy² ≤ r² is exact for integer coordinates. For large inputs with many queries, consider spatial indexing (k-d tree, grid bucketing). Practice this pattern: "count points in rectangle," "count points in polygon" — all use the same squared-distance comparison principle.