Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google coding round, one problem that mashes together two classic LC problems in a way that feels obvious in hindsight but took me a minute to see during the actual interview.

Questions Asked (1)

Given a list of 2D points that may include duplicates and an integer k, return the k points with the highest frequency. Break ties by choosing points closer to the origin.

Algorithms & Data Structures

Author's notes

I recognized the 'top k' pattern pretty fast but spent too long second-guessing the tie-breaking part.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, count the frequency of each unique point using a hash map. Then, sort the unique points by frequency descending and distance ascending, and return the first k points. Alternatively, use a heap to efficiently select the top k points without sorting all unique points.

Pro tip: Clarify whether the output order matters and whether k can exceed the number of unique points. Also, mention that you can avoid sorting all points by using a min-heap of size k, which is more efficient when k is much smaller than the number of unique points.

1. Clarify requirements and edge cases

Ask about input size, whether k is guaranteed to be ≤ number of unique points, and if the output order matters. Discuss handling duplicates and ties.

2. Count frequencies

Iterate through the list and use a hash map to count the frequency of each unique point. This takes O(n) time.

3. Define comparison criteria

For each unique point, compute its distance squared from the origin. The sorting order is: higher frequency first; if frequencies are equal, smaller distance first.

4. Select top k points

Use a min-heap of size k to efficiently select the top k points based on the comparison criteria, or sort all unique points if k is close to the number of unique points.

5. Return result

Extract the points from the heap (or sorted list) and return them. If order doesn't matter, return as is; otherwise, sort appropriately.

Key Points to Mention

Hash map for frequency counting
Distance squared to avoid floating-point precision issues
Custom comparator for sorting or heap ordering
Time complexity: O(n + m log k) with heap, or O(n + m log m) with sorting, where m is number of unique points
Space complexity: O(m) for hash map and heap
Handling ties by distance and potential edge cases like k > unique points

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.