Find All Points Within a Radius
Google● MediumFULLTIMEPHONE SCREENProblem statement
You are given a list of points in the plane, points, where points[i] = [x, y] is point i, and a fixed integer radius. For a query point (qx, qy), a point (x, y) is inside the circle when its distance to the query point is at most radius, that is, when (x - qx)^2 + (y - qy)^2 <= radius^2. Points exactly on the circle count as inside.
You are also given many queries, queries, where queries[j] = [qx, qy]. Every query uses the same points and the same radius, so it pays to prepare the points once and answer each query quickly.
The problem statement continues
ProExamples
Example 1
points = [[0,0],[3,4],[6,8],[-3,-4],[1,1]]radius = 5queries = [[0,0],[6,8],[10,10]]return = [[0,1,3,4],[1,2],[2]]- Around
(0, 0): point1at(3, 4)and point3at(-3, -4)are exactly 5 away, on the circle, so they count. Point0is at distance 0 and point4at about 1.41. Point2is 10 away. The answer is[0,1,3,4]. - Around
(6, 8): point2is the query point itself and point1is exactly 5 away. Point4at(1, 1)is about 8.6 away. The answer is[1,2]. - Around
(10, 10): only point2is close enough, at about 4.47. The answer is[2].
FastPrep Pro
Reported in 1 Google interview this weekUnlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$8.25/month
$99 billed yearly — or $19 month-to-month. Cancel anytime.
Free plan — 2 of 2 free unlocks used this week