Chapter 4 · 10 min
Gaps, islands, and completeness
Two hard interview patterns do not look alike but share a structure: they ask whether a set is complete or contiguous. Both are worth learning as shapes rather than memorising as queries.
Gaps and islands
“Find consecutive days of activity” is an islands question. The standard trick assigns a constant group key to every consecutive run: subtract a row number from the date, and every row in a run produces the same key because the date and the row number advance together.
WITH days AS (
SELECT DISTINCT customer_id, order_date
FROM orders
),
islands AS (
SELECT
customer_id,
order_date,
order_date - (row_number() OVER (
PARTITION BY customer_id ORDER BY order_date
))::int AS island_key
FROM days
)
SELECT
customer_id,
min(order_date) AS streak_start,
max(order_date) AS streak_end,
count(*) AS days
FROM islands
GROUP BY customer_id, island_key
HAVING count(*) >= 2
ORDER BY customer_id ASC, streak_start ASC;
The DISTINCT matters: without it, several orders on the same day would break the arithmetic and
the run would look shorter than it is. The cast to int keeps the subtraction a date operation
rather than an interval.
A recursive CTE can walk the sequence too, but the row-numbering form is shorter, works on any supported Postgres, and is what interviewers expect to see.
Relational division
“Customers who bought every category” is a completeness question. The direct answer compares a per-customer distinct count with the size of the full set:
SELECT o.customer_id
FROM orders AS o
JOIN order_items AS oi ON oi.order_id = o.order_id
JOIN products AS p ON p.product_id = oi.product_id
GROUP BY o.customer_id
HAVING count(DISTINCT p.category) = (SELECT count(DISTINCT category) FROM products);
The comparison must use count(DISTINCT ...) on both sides. count(*) counts order lines, so a
customer who bought five items from one category would appear to have “five categories”.
The double-NOT EXISTS formulation expresses the same idea without an aggregate: there is no
category for which no matching purchase exists. It is longer and harder to read, but it generalises
to predicates that cannot be counted.
The NOT IN trap
A tempting shortcut is WHERE category NOT IN (SELECT category FROM purchases WHERE ...). If the
subquery can produce a NULL, NOT IN returns no rows at all, because x <> NULL is unknown
rather than true. Use NOT EXISTS, or filter NULL out of the subquery explicitly. This trap is
common enough that reviewers look for it by name.
What the chapter quiz checks
The quiz at the end of this chapter covers window-versus-group semantics, the difference between
row_number, rank, and dense_rank, where a rank filter belongs, the first-row result of lag,
and the correct shape of a relational-division query.