Queries on Number of Points Inside a Circle
Asked at Anduril
Problem
Queries on Number of Points Inside a Circle gives you points and circle queries (x, y, r), and asks, for each circle, how many points lie inside or on it. With at most 500 points and 500 queries, a direct check per pair is the intended solution — the interview value is in doing the geometry cleanly with integers.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
A point (px, py) is inside or on the circle iff (px - x)² + (py - y)² <= r².
Compare squared distances. Taking a square root is slower and can misclassify boundary points due to floating-point error.
For each query, loop over all points and count the ones that pass the check: O(points * queries) = 250,000 checks at most.
Follow-up (if the interviewer asks about scale): sort points by x and only check those with x - r <= px <= x + r, or use a spatial grid/k-d tree.
Walkthrough: point (1,3), circle (2,3,1): (1-2)² + 0 = 1 <= 1 -> on the boundary, counted.
Optimal Approach
Step 1: For each query (x, y, r):
cnt = number of points with (px - x)² + (py - y)² <= r².
Append cnt.
Step 2: Return the counts.
Time: O(p * q). Space: O(q) for the output.
What Trips People Up in Real Interviews
Using sqrt and floating-point comparisons. Squared integer distances are exact.
Using < instead of <= — points on the boundary count.
Over-engineering a spatial index for 500 points. Mention it as a follow-up for larger inputs.
Mixing up which array holds circles and which holds points.
Solution Code
def countPoints(points, queries):
res = []
for x, y, r in queries:
r2 = r * r
cnt = 0
for px, py in points:
if (px - x) ** 2 + (py - y) ** 2 <= r2:
cnt += 1
res.append(cnt)
return resFrequently Asked Questions
What is the Queries on Number of Points Inside a Circle problem?
Queries on Number of Points Inside a Circle gives you points and circle queries `(x, y, r)`, and asks, for each circle, how many points lie inside or on it. With at most 500 points and 500 queries, a direct check per pair is the intended solution — the interview value is in doing the geometry cleanly with integers.
How do you solve Queries on Number of Points Inside a Circle?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Queries on Number of Points Inside a Circle?
Queries on Number of Points Inside a Circle is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Queries on Number of Points Inside a Circle?
- Using `sqrt` and floating-point comparisons. Squared integer distances are exact.
- Using `<` instead of `<=` — points on the boundary count.
- Over-engineering a spatial index for 500 points. Mention it as a follow-up for larger inputs.
- Mixing up which array holds circles and which holds points.