Maximum Unique-Tagged Points in an Origin-Centred Circle
Updated
Problem statement
Point i has coordinates (X[i], Y[i]) and tag S[i]. Choose any real radius greater than or equal to zero for a circle centered at (0, 0).
Every point inside or on the boundary belongs to the circle. The included points must all have different tags; you cannot omit an individual point that the circle contains.
Return the maximum number of points in a valid circle. You may choose radius zero. Since no input point is at the origin, this allows a circle containing no points.
Function
solution(S: String, X: int[], Y: int[]) → intExamples
Example 1
S = "ABDCA"X = [2,-1,-4,-3,3]Y = [2,-2,4,1,-3]return = 3Include the points tagged B, A and C at squared distances 5, 8 and 10. Reaching squared distance 18 would also include a second A.
Example 2
S = "ABB"X = [1,-2,-2]Y = [1,-2,2]return = 1Both B points have squared distance 8, so a valid circle stops before them and keeps only A.
Example 3
S = "CCD"X = [1,-1,2]Y = [1,-1,-2]return = 0The two nearest points both have tag C and squared distance 2. A valid circle therefore contains no points.
Constraints
- For this exercise, assume
1 <= S.length <= 100000, withX.length = Y.length = S.length. - For this exercise, assume tags are uppercase English letters.
- For this exercise, assume
-10^9 <= X[i], Y[i] <= 10^9, and no input point equals(0, 0).
More Marshall Wace Online Assessment questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
- Count Distinct Tags in a Fixed-Radius Circle (Practice Reconstruction)OA · Seen Apr 2024
- Generate Unique Company Email AddressesOA · Seen Apr 2024
- Reconstruct a Two-Row Binary MatrixOA · Seen Apr 2024
Similar questions at other companies
- HTTP Request RedirectionAmazon · OA
- Find All Points Within a RadiusGoogle · PHONE SCREENGoogle interview questions
- Merge Collinear Point SegmentsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Count Overlapping Square PairsRamp · OARamp interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Count Servers With No Requests in a Time WindowIBM · OAIBM interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Build Sessions from Unordered Events (Part 1)Scale AI · OAScale AI interview questions
- Minimum Distinct Prefix CostChubb · OAChubb interview questions
- Decode Words with Anagram KeysCresta · OACresta interview questions