How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Streaming Points: Remove Any Pair Within a Distance

Quick Overview

This question evaluates practical use of ordered data structures for streaming input with proximity-based removal logic. It tests balanced BST or sorted-set operations, floating-point comparison handling, and greedy pair selection — skills commonly assessed in algorithm-focused software engineering interviews.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Streaming Points: Remove Any Pair Within a Distance You are given a continuous stream of points on a number line. Each incoming value is a `double` representing a position. You maintain a collection of the points seen so far that have not yet been removed. After inserting each new point, check whether the current collection contains **any two distinct points whose absolute difference is at most `d`** (a given distance threshold). If such a pair exists, **remove that pair** from the collection and emit it. Continue removing pairs (and emitting them) until no qualifying pair remains, then process the next stream value. When more than one valid pair could be removed, prefer the pair with the **smallest positions** — i.e. repeatedly take the two smallest remaining points whenever they are within `d` of each other. ## Input - `stream`: a list of `double` values, processed left to right. - `d`: a non-negative `double` distance threshold. ## Output - A list of emitted pairs, in the order they were removed. Each pair is `[a, b]` with `a <= b` and `b - a <= d`. ## Floating-point note - Comparisons of `double` values must tolerate floating-point error. Treat two values as "within `d`" when `b - a <= d + eps` for a small epsilon (e.g. `1e-9`), and consider equal positions to be distinct points (duplicates allowed in the collection). ## Example ``` Input: stream = [1.0, 5.0, 1.4, 4.9], d = 0.5 Output: [[1.0, 1.4], [4.9, 5.0]] ``` Explanation: After `1.0, 5.0` no pair is within `0.5`. Inserting `1.4`: the two smallest are `1.0` and `1.4` (difference `0.4 <= 0.5`) — remove and emit `[1.0, 1.4]`. Remaining: `{5.0}`. Inserting `4.9`: `5.0 - 4.9 = 0.1 <= 0.5` — remove and emit `[4.9, 5.0]`. ## Constraints - `1 <= len(stream) <= 10^5` - `0 <= d <= 10^9` - Use an ordered structure so that after each insertion you can find the closest neighbors efficiently rather than rescanning all points. ## Follow-up to consider in your design - **Groups of K:** Generalize so that instead of removing a *pair*, you remove a *group of `K` points* whenever `K` currently-held points all lie within a window of width `d` (i.e. `max - min <= d` across the group). Emit and remove the group, then re-check.

Quick Answer: This question evaluates practical use of ordered data structures for streaming input with proximity-based removal logic. It tests balanced BST or sorted-set operations, floating-point comparison handling, and greedy pair selection — skills commonly assessed in algorithm-focused software engineering interviews.

You are given a continuous stream of points on a number line. Each incoming value is a `double` representing a position. You maintain a collection of the points seen so far that have not yet been removed. After inserting each new point, check whether the current collection contains **any two distinct points whose absolute difference is at most `d`** (a given distance threshold). If such a pair exists, **remove that pair** from the collection and emit it. Continue removing pairs (and emitting them) until no qualifying pair remains, then process the next stream value. When more than one valid pair could be removed, prefer the pair with the **smallest positions** — i.e. repeatedly take the two smallest remaining points whenever they are within `d` of each other. ## Input - `stream`: a list of `double` values, processed left to right. - `d`: a non-negative `double` distance threshold. ## Output - A list of emitted pairs, in the order they were removed. Each pair is `[a, b]` with `a <= b` and `b - a <= d`. ## Floating-point note Comparisons of `double` values must tolerate floating-point error. Treat two values as "within `d`" when `b - a <= d + eps` for a small epsilon (e.g. `1e-9`), and consider equal positions to be distinct points (duplicates allowed in the collection). ## Example ``` Input: stream = [1.0, 5.0, 1.4, 4.9], d = 0.5 Output: [[1.0, 1.4], [4.9, 5.0]] ``` After `1.0, 5.0` no pair is within `0.5`. Inserting `1.4`: the two smallest are `1.0` and `1.4` (difference `0.4 <= 0.5`) — remove and emit `[1.0, 1.4]`. Remaining: `{5.0}`. Inserting `4.9`: `5.0 - 4.9 = 0.1 <= 0.5` — remove and emit `[4.9, 5.0]`. ## Follow-up (design discussion) **Groups of K:** Generalize so that instead of removing a *pair*, you remove a *group of `K` points* whenever `K` currently-held points all lie within a window of width `d` (i.e. `max - min <= d` across the group). Emit and remove the group, then re-check.

Constraints

1 <= len(stream) <= 10^5
0 <= d <= 10^9
Each stream value is a double (positions may repeat; equal positions are distinct points).
Use an ordered structure (TreeSet / TreeMap / balanced BST / sorted container / min-heap) so closest neighbors are found without rescanning all points.
Tolerate floating-point error: treat b - a <= d + eps (eps = 1e-9) as within d.

Examples

Input: ([1.0, 5.0, 1.4, 4.9], 0.5)

Expected Output: [[1.0, 1.4], [4.9, 5.0]]

Explanation: Worked example: 1.4 pairs with 1.0 (gap 0.4); later 4.9 pairs with 5.0 (gap 0.1).

Input: ([], 0.5)

Expected Output: []

Explanation: Empty stream — nothing to insert or emit.

Input: ([3.0], 1.0)

Expected Output: []

Explanation: A single point can never form a pair.

Input: ([2.0, 2.0], 0.0)

Expected Output: [[2.0, 2.0]]

Explanation: Equal positions are distinct points; gap 0 <= d=0, so they pair and are emitted.

Input: ([0.0, 10.0, 20.0], 0.5)

Expected Output: []

Explanation: No two held points are ever within 0.5.

Input: ([1.0, 2.0, 3.0, 4.0], 1.0)

Expected Output: [[1.0, 2.0], [3.0, 4.0]]

Explanation: 2.0 pairs with 1.0 (gap 1.0); 4.0 pairs with 3.0 (gap 1.0). 3.0 is alone when inserted (1.0,2.0 already gone).

Input: ([5.0, 1.0, 1.5, 5.4], 0.5)

Expected Output: [[1.0, 1.5], [5.0, 5.4]]

Explanation: Smallest-first: 1.5 pairs with 1.0 before any 5.x pair; then 5.4 pairs with 5.0.

Input: ([1.0, 1.1, 1.2], 0.15)

Expected Output: [[1.0, 1.1]]

Explanation: 1.1 pairs with 1.0 (gap 0.1). When 1.2 arrives it is alone, so no further pair.

Input: ([-3.0, -2.5, -2.4], 0.6)

Expected Output: [[-3.0, -2.5]]

Explanation: Negatives: -2.5 pairs with -3.0 (gap 0.5). -2.4 is then alone.

Input: ([0.0, 0.0, 0.0, 0.0], 0.0)

Expected Output: [[0.0, 0.0], [0.0, 0.0]]

Explanation: Four identical points form two pairs as duplicates are inserted; each pair has gap 0 <= d=0.

Hints

Keep the held points in a sorted/ordered structure. The pair with the smallest positions is always the two smallest currently-held points, so you only ever need to look at the front of the order.
After each insertion, loop: while at least two points remain and (second_smallest - smallest) <= d + eps, emit and remove both, then re-check the new two smallest.
A newly inserted point can trigger a chain of removals, but each point is removed at most once overall, so the total work across the whole stream is bounded.
For floating-point safety, compare with an epsilon (b - a <= d + 1e-9) and remember that two equal positions still count as two distinct points.

Quick Overview