Find All Numbers that Appear at Least Three Times Consecutively

To find numbers appearing at least three times consecutively, utilize SQL window functions to create a unique group identifier for each sequence of identical, consecutive numbers. Then, filter these groups based on their count.

Mechanics and Why It Works

The core idea is to leverage the difference between two ROW_NUMBER() calculations. Assume an id column exists to define the order of "consecutive" entries.

When you subtract the partitioned row number from the overall row number (ROW_NUMBER() OVER (ORDER BY id) - ROW_NUMBER() OVER (PARTITION BY num ORDER BY id)), a constant grp value is generated for all rows that are part of the same consecutive sequence of num. This is because for a consecutive block of identical numbers, both ROW_NUMBER() functions increment in lockstep, maintaining a constant difference. When the num changes, the ROW_NUMBER() OVER (PARTITION BY num ...) resets, causing the difference to change, thus creating a new grp for the next consecutive block.

Example and Trade-offs

WITH NumberGroups AS (
    SELECT
        id,
        num,
        (ROW_NUMBER() OVER (ORDER BY id) - ROW_NUMBER() OVER (PARTITION BY num ORDER BY id)) AS grp
    FROM
        Logs -- Assuming 'Logs' is your table and 'id' defines order
)
SELECT DISTINCT num
FROM NumberGroups
GROUP BY num, grp
HAVING COUNT(*) >= 3;

This approach is generally efficient for moderate datasets. For very large datasets, window functions, especially those with PARTITION BY and ORDER BY clauses, can be computationally intensive. They often require significant data shuffling (e.g., in distributed systems like Spark) and sorting, which can impact performance. The ORDER BY id clause is crucial for defining "consecutive" and can be a bottleneck if the ordering column is not indexed or if the data is highly unsorted.

In the interview, also mention…

Emphasize the critical role of an ordering column (e.g., id, timestamp) to properly define "consecutive." Discuss the performance implications of window functions on large-scale data and potential optimizations like ensuring appropriate indexing or understanding data distribution to minimize shuffle.