Interview Prep
SQL Coding Challenges — Top-N, Gaps, Deduplication
This lesson covers fundamental data manipulation patterns required for advanced SQL interviewing. Mastering these techniques allows you to filter subsets of data, identify missing sequences, and refine datasets to a unique state. These skills are essential for real-world reporting, data cleaning, and performance optimization tasks.
Understanding Deduplication
Deduplication is the process of removing redundant records that often arise from improper joins or data ingestion issues. The most robust way to handle this in SQL is through Common Table Expressions (CTEs) combined with window functions like ROW_NUMBER(). By partitioning the data by a unique business key and ordering it by a specific column, you can assign a unique integer to each duplicate row. When you filter where this number equals one, you effectively isolate the 'latest' or 'primary' record while discarding the noise. This approach is superior to using DISTINCT because it allows you to retain specific metadata from the chosen duplicate, rather than just forcing uniqueness across the entire row. Understanding why this works requires grasping how window functions evaluate sets within a partition, providing a deterministic way to filter messy data inputs without damaging the underlying relational integrity.
-- Deduplicate orders by keeping only the most recent entry per customer
WITH RankedOrders AS (
SELECT *,
ROW_NUMBER() OVER(PARTITION BY customer_id ORDER BY order_date DESC) as rn
FROM orders
)
SELECT * FROM RankedOrders WHERE rn = 1; -- Keep only the latest recordImplementing Top-N Per Group
Top-N analysis involves finding the highest or lowest values within categorical subgroups, such as the top three products sold per category. Unlike a simple global order, this requires a partitioned window approach. Using DENSE_RANK() or ROW_NUMBER() allows the engine to reset the sorting criteria for every category present in the dataset. DENSE_RANK is particularly useful when you need to handle ties, as it assigns the same rank to equal values, whereas ROW_NUMBER ensures a distinct ordering even in identical cases. The logic works because the window function creates a frame that is evaluated independently for each partition defined in the OVER clause. This is the bedrock of analytical queries where stakeholders demand 'top performers' or 'worst failures' across multiple departments, allowing for scalable, maintainable code that avoids complex and slow correlated subqueries.
-- Get top 3 revenue-generating products per category
SELECT category_id, product_name, revenue
FROM (
SELECT *,
DENSE_RANK() OVER(PARTITION BY category_id ORDER BY revenue DESC) as ranking
FROM product_sales
) t
WHERE ranking <= 3; -- Filter after ranking is assignedSolving the Gaps and Islands Problem
The Gaps and Islands problem involves identifying continuous ranges of data and detecting missing values within sequences. This is conceptually challenging because standard SQL is row-based, while sequences are relationship-based. To solve this, we create 'islands' by subtracting a row number from the sequence value itself. Within a continuous sequence, the difference between the actual value and its sequential rank remains constant. When the sequence breaks, the difference shifts, creating a new group. By grouping by this calculated difference, you can define the start and end of every sequence. This technique is brilliant because it transforms a non-linear problem into a standard aggregation task. Understanding this allows you to reason about time-series data, such as tracking how many days a user has consecutively logged in or identifying breaks in scheduled events without needing procedural logic.
-- Identify gaps in a sequence of numeric IDs
SELECT MIN(id) as start_range, MAX(id) as end_range
FROM (
SELECT id, id - ROW_NUMBER() OVER(ORDER BY id) as grp
FROM sequence_table
) t
GROUP BY grp; -- Constant 'grp' indicates a contiguous islandAnalyzing Running Totals and Aggregates
Running totals, or cumulative sums, provide a historical view of growth or depletion over time. By using a window function with an ORDER BY clause inside the OVER function, you dictate that the sum calculation should include all rows from the start of the partition up to the current row. This is powerful because it allows you to visualize trends without collapsing the dataset into a single summary row. The reason this works is that the window frame default is UNBOUNDED PRECEDING, which tells the database to maintain a memory-efficient tally as it iterates through the ordered set. If you need to restart the running total for each customer or department, simply add a PARTITION BY clause. This pattern is indispensable for financial modeling, inventory tracking, and performance reporting where the path to the current value is as important as the value itself.
-- Calculate daily running total of revenue
SELECT transaction_date, revenue,
SUM(revenue) OVER(ORDER BY transaction_date ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) as running_total
FROM daily_sales;Complex Filtering with Window Functions
Finally, we must combine window functions with aggregation to solve complex business logic, such as finding values that deviate significantly from a group average. By calculating an average over a partition and then selecting only those rows that exceed a specific threshold relative to that average, you create a sophisticated filter. This approach is superior to joining aggregate tables back to the main table because it keeps the logic contained in a single pass over the data, which is highly efficient. When writing these, always consider the order of operations: the window function computes its result based on the defined partition after the WHERE clause has filtered the initial source, but before the final SELECT projection. This gives you a powerful toolset for identifying outliers, flagging fraud, or performing advanced benchmarking without losing context of the individual records being inspected.
-- Find sales that are 20% higher than the category average
SELECT * FROM (
SELECT *,
AVG(amount) OVER(PARTITION BY category) as avg_cat_amount
FROM sales_data
) t
WHERE amount > (avg_cat_amount * 1.2); -- Filter based on window aggregateKey points
- Deduplication relies on window functions to deterministicly isolate unique records.
- ROW_NUMBER is ideal for unique identification, while DENSE_RANK handles ties gracefully.
- Partitioning logic allows you to perform calculations within distinct subgroups simultaneously.
- The Gaps and Islands technique uses constant difference subtraction to detect continuity.
- Running totals leverage the window frame clause to track accumulation over time.
- Window functions are evaluated after basic filtering but before the final output.
- Always define your partitioning and ordering criteria carefully to avoid incorrect aggregates.
- Combining window functions with traditional filters avoids the performance cost of multiple joins.
Common mistakes
- Mistake: Using LIMIT to get the 'top N' per category. Why it's wrong: LIMIT applies to the whole result set, not groups. Fix: Use window functions like DENSE_RANK() or ROW_NUMBER() partitioned by the category.
- Mistake: Assuming a gap exists only if ID+1 is missing. Why it's wrong: This logic fails if IDs are not strictly sequential or if multiple rows are deleted. Fix: Use the LEAD() function to compare the current value with the next value.
- Mistake: Using DISTINCT for deduplication without identifying a unique key. Why it's wrong: DISTINCT removes duplicates based on the entire row, not just specific columns. Fix: Use a Common Table Expression (CTE) with ROW_NUMBER() to target specific duplicate records.
- Mistake: Using subqueries for Top-N tasks in older SQL versions. Why it's wrong: Correlated subqueries are inefficient and hard to read. Fix: Use modern Window Functions which execute in a single pass over the data.
- Mistake: Forgetting to handle NULLs when identifying gaps. Why it's wrong: Comparing NULL to a value using standard operators results in UNKNOWN, causing rows to be filtered out. Fix: Use COALESCE() to provide a default value when performing gap analysis.
Interview questions
How would you approach removing duplicate records from a table that does not have a primary key?
To remove duplicates in a table without a primary key, the most effective method is using a Common Table Expression (CTE) with the ROW_NUMBER() window function. By partitioning the data by all columns and ordering by any column, we assign a unique integer to each row within its partition. We then perform a DELETE operation on the CTE, targeting rows where the assigned row number is greater than one. This ensures that only one instance of the duplicate remains while others are safely purged from the physical storage.
How do you identify missing values in a sequential range, such as finding gaps in a sequence of order IDs?
Finding gaps requires identifying where the difference between the current row and the next row is greater than one. You can use the LEAD() window function to compare the current value with the subsequent value in the sequence. By calculating the difference, you can filter for rows where this difference is greater than one. This approach is highly performant because it avoids self-joins, scanning the table linearly to pinpoint exactly where the sequence breaks and revealing the missing numerical intervals.
How do you retrieve the 'Top-N' records per category, such as the top three highest-paid employees in each department?
To retrieve the Top-N records per category, you should use the DENSE_RANK() or ROW_NUMBER() window function partitioned by the category column and ordered by the value column in descending order. By wrapping this in a subquery or CTE, you can filter for results where the rank is less than or equal to N. This is the industry-standard approach because it is far more scalable than using correlated subqueries, which would require an expensive lookup for every single row in the dataset.
Can you compare using a self-join versus using window functions to solve a 'gaps and islands' problem?
A self-join approach involves joining a table to itself on a condition like T1.id = T2.id + 1, which identifies contiguous sequences but becomes extremely slow as table size increases due to the O(n²) complexity. Conversely, window functions like LAG() or calculating the difference between a ROW_NUMBER() and the actual sequence value allow you to identify gaps in linear time. Window functions are significantly more efficient because they process the data in a single pass rather than creating massive intermediate join results.
How can you effectively determine the 'islands' in a data sequence, where groups of consecutive numbers are separated by gaps?
Islands can be identified by subtracting a row number from the actual sequence value. When the sequence is continuous, the difference between the value and its row number remains constant. If a gap occurs, that constant value jumps, creating a new group. By grouping by this calculated difference, you effectively collapse contiguous blocks of data into a single island. This technique is elegant because it turns a complex grouping problem into a simple arithmetic derivation, requiring no iterative loops or cursors.
Explain how to perform a 'Top-N' query efficiently when you must handle ties, and why your chosen function matters.
Handling ties depends on whether you want to include all tied records or just a subset. Using ROW_NUMBER() will assign a unique rank to tied records arbitrarily, ensuring you get exactly N rows, which is useful for pagination. However, using DENSE_RANK() or RANK() allows you to include all tied records in your top results. Choosing the correct function is critical for business logic; for example, if ranking bonus recipients, DENSE_RANK() is fairer because it does not penalize employees who happen to have the exact same performance score as a colleague.
Check yourself
1. Which approach is most efficient for finding the 'top 3' sales per department?
- A.A self-join on the sales table comparing values
- B.A window function using DENSE_RANK() partitioned by department
- C.Multiple UNION ALL statements for each department
- D.Using a correlated subquery in the WHERE clause
Show answer
B. A window function using DENSE_RANK() partitioned by department
Window functions are purpose-built for ranking within partitions. Self-joins perform poorly on large datasets, UNION ALL is unmaintainable, and correlated subqueries trigger row-by-row processing, which is slow.
2. To identify gaps in a sequence of numbers, which function is the most effective for comparing a row with its successor?
- A.LAG()
- B.LEAD()
- C.RANK()
- D.NTILE()
Show answer
B. LEAD()
LEAD() accesses data from the following row, allowing you to compare current and next values. LAG() looks backwards, RANK() ranks rows, and NTILE() buckets data, none of which directly simplify gap analysis as well as LEAD().
3. When deleting duplicate rows based on a specific column, why is a CTE with ROW_NUMBER() preferred over DISTINCT?
- A.DISTINCT cannot be used in a DELETE statement
- B.ROW_NUMBER() is faster than DISTINCT
- C.DISTINCT removes the entire row, whereas ROW_NUMBER() allows you to target one record to keep while removing others
- D.DISTINCT requires a GROUP BY clause that prevents deletion
Show answer
C. DISTINCT removes the entire row, whereas ROW_NUMBER() allows you to target one record to keep while removing others
DISTINCT filters unique result sets but cannot pinpoint specific duplicates for deletion. ROW_NUMBER() assigns a unique identifier to duplicates, allowing you to isolate one record to keep (e.g., where row_num = 1) and delete the rest.
4. What is the primary risk of using 'ID = ID + 1' to find gaps in a sequence?
- A.It only works if the table has an auto-incrementing primary key
- B.It performs a full table scan that is computationally expensive
- C.It fails if the sequence has multiple missing numbers in a row
- D.It creates a Cartesian product that crashes the database
Show answer
C. It fails if the sequence has multiple missing numbers in a row
Checking ID+1 only identifies immediate next-neighbor gaps. If two or more consecutive IDs are missing, this logic fails to identify the magnitude of the gap, whereas set-based comparison via LEAD() is more robust.
5. When ranking items with tied values, what is the functional difference between ROW_NUMBER() and DENSE_RANK()?
- A.ROW_NUMBER() generates consecutive integers; DENSE_RANK() leaves gaps in ranking for tied values
- B.ROW_NUMBER() leaves gaps; DENSE_RANK() generates consecutive integers
- C.DENSE_RANK() requires an ORDER BY clause, while ROW_NUMBER() does not
- D.ROW_NUMBER() is faster because it does not handle ties
Show answer
B. ROW_NUMBER() leaves gaps; DENSE_RANK() generates consecutive integers
ROW_NUMBER() provides unique sequential integers even for ties. DENSE_RANK() assigns the same rank to ties but does not skip the next rank, making it 'dense' compared to standard RANK(), which does skip ranks after ties.