The Space Between Us

A hard SQL interview practice problem on DataDriven. Write the query and run it against a real database, with instant feedback.

Domain

SQL

Difficulty

hard

Seniority

L5

Asked in

Meta

Problem

We run an ad platform and want to measure how much any two users overlap in the campaigns that actually earned revenue from them. For each pair of users sharing at least one such campaign, report how many campaigns earned from both and the overlap ratio: campaigns that earned from both divided by campaigns that earned from either, rounded to two decimals. Walk the pairs from the lowest user id up to the highest, and where the first user is the same, from that user's lowest partner id up to the highest.

Every viewer lives inside a world of campaigns. Measure how much two of those worlds are really one.

Tables

ad_impressions

Columns: impression_id INTEGER, user_id INTEGER, ad_campaign TEXT, impression_time TEXT, clicked INTEGER, revenue REAL

Expected output

Worked solution and explanation

What this problem really is

Strip off the ad-targeting costume and this is Jaccard set similarity computed for every pair of users. The real question: can you express 'how much do two people overlap' as a self-join over a deduplicated (user, campaign) set, without letting repeat impressions inflate the overlap or counting each pair twice? Anyone can join the table to itself. What separates candidates is the DISTINCT before the join and the a.user_id < b.user_id guard, plus remembering to keep only the campaigns that actually earned revenue. Skip the DISTINCT and a user who saw one campaign forty times looks like forty shared campaigns. Leave the no-revenue impressions in and you count campaigns a user never monetized. Skip the inequality and every pair appears twice, plus every user pairs with themselves. Then the denominator: the overlap is shared campaigns over the union of both sets, count_a + count_b - shared, not over either set alone.

Break down the requirements

Step 1: Get each user's revenue-earning campaigns

SELECT DISTINCT user_id, ad_campaign FROM ad_impressions collapses raw impressions into unique (user, campaign) memberships. Filter to revenue IS NOT NULL right here: a campaign that never earned revenue from a user does not belong in that user's set.

Step 2: Self-join to find shared campaigns

Join the distinct set to itself on ad_campaign with a.user_id < b.user_id. The inequality does double duty: it removes self-pairs and keeps each unordered pair exactly once.

Step 3: Count shared and compute the overlap ratio

Group by the pair, count the shared campaigns, and divide by (count_a + count_b - shared_campaigns), the number of campaigns at least one of the two users earned on, where each count comes from a small helper set of per-user campaign totals. Round to two decimals for the dashboard.

The solution

WITH user_campaigns AS (
    SELECT DISTINCT user_id, ad_campaign
    FROM ad_impressions
    WHERE revenue IS NOT NULL
),
user_counts AS (
    SELECT user_id, COUNT(*) AS campaign_count
    FROM user_campaigns
    GROUP BY user_id
)
SELECT
    a.user_id AS user_id_1,
    b.user_id AS user_id_2,
    COUNT(*) AS shared_campaigns,
    ROUND(COUNT(*) * 1.0 / (uc1.campaign_count + uc2.campaign_count - COUNT(*)), 2) AS overlap_ratio
FROM user_campaigns a
JOIN user_campaigns b ON a.ad_campaign = b.ad_campaign AND a.user_id < b.user_id
JOIN user_counts uc1 ON a.user_id = uc1.user_id
JOIN user_counts uc2 ON b.user_id = uc2.user_id
GROUP BY a.user_id, b.user_id, uc1.campaign_count, uc2.campaign_count
ORDER BY a.user_id, b.user_id

Common follow-up questions

• How would you compute containment similarity instead of Jaccard? (Denominator becomes the smaller of the two counts; in SQLite there is no LEAST, so use the two-argument MIN(a, b) scalar to take the smaller-of-two.)
• What if you only wanted pairs with overlap above 50 percent? (Add a HAVING on the ratio after grouping.)
• How would this scale with 15 million users? (The self-join is O(n^2) in the worst case; discuss sampling, MinHash, or approximate methods.)
• What if you wanted overlap among campaigns users merely clicked, revenue or not? (Swap the revenue filter for clicked = 1 and the set changes to engaged-but-not-necessarily-paying campaigns.)