Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Google SWE coding round with a tricky streaming data structure problem. The core idea sounds manageable until you actually try to implement it cleanly under pressure.

Questions Asked (1)

You're given a stream of doubles representing positions on a number line. After each insertion into your collection, check if any two points are within distance d of each other. If so, remove and emit the pair with the two smallest positions, and keep doing that until no qualifying pair remains. Handle floating-point comparisons with a small epsilon. What data structure do you use and how do you implement this efficiently?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was a sorted list and binary search for neighbors, which is the right direction, but I fumbled on the 'keep removing until none left' loop.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a balanced binary search tree (e.g., TreeSet in Java) to maintain sorted order of points, allowing O(log n) insertion and neighbor checks. After each insertion, check the immediate predecessor and successor for distance ≤ d + epsilon; if a pair is found, remove the two smallest positions, emit them, and repeat until no qualifying pair remains.

Pro tip: Explicitly discuss how you handle floating-point comparisons with epsilon, and mention that using a TreeSet with a custom comparator that treats values within epsilon as equal can simplify duplicate handling and ensure consistency.

1. Clarify requirements and constraints

Confirm the definition of 'within distance d' (inclusive or exclusive), the epsilon value, and whether the stream is unbounded. Discuss expected input size and performance requirements.

2. Choose the right data structure

Select a balanced BST (e.g., TreeSet) to maintain sorted order and support efficient predecessor/successor queries. Explain why a heap or hash map alone is insufficient.

3. Insert and check neighbors

On each insertion, find the immediate predecessor and successor. Check if the distance to either is ≤ d + epsilon. If so, identify the pair with the two smallest positions.

4. Remove and emit pairs iteratively

Remove the qualifying pair, emit it, and then check if the removal creates a new qualifying pair between the predecessor of the smaller and the successor of the larger. Repeat until no such pair exists.

5. Handle floating-point precision

Use an epsilon in all distance comparisons. Consider a custom comparator that treats values within epsilon as equal to avoid duplicates and ensure consistent ordering.

Key Points to Mention

Balanced BST (e.g., TreeSet) provides O(log n) insertion, deletion, and neighbor lookup.
Only need to check immediate neighbors because if any pair is within d, the closest pair will be adjacent in sorted order.
After removal, only the new adjacency between the predecessor of the removed smaller element and the successor of the removed larger element can create a new qualifying pair.
Use epsilon in comparisons: distance ≤ d + epsilon to account for floating-point errors.
Custom comparator that considers values within epsilon as equal can prevent issues with near-duplicate points.
Time complexity: O(n log n) overall, as each insertion and removal is O(log n) and each point is inserted and removed at most once.

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