# The Space Between Us > Every viewer lives inside a world of campaigns. Measure how much two of those worlds are really one. Canonical URL: Domain: SQL · Difficulty: hard · Seniority: L5 ## Problem We run an ad platform and want to know how much any two users overlap in the campaigns they were shown. For each pair of users that shares at least one campaign, report the overlap ratio: the number of campaigns both saw, divided by the number of campaigns at least one of them saw, rounded to two decimals. ## 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. Skip the DISTINCT and a user who saw one campaign forty times looks like forty shared campaigns. 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. > **Trick to solving** > > The overlap is Jaccard similarity: intersection over union. Four moves: get the distinct campaigns per user, self-join to find campaigns two users share, count the shared campaigns per pair, then divide by the union size, count_a plus count_b minus shared. --- ### Break down the requirements #### Step 1: Get distinct campaigns per user SELECT DISTINCT user_id, ad_campaign FROM ad_impressions collapses 400M raw impressions into unique (user, campaign) memberships. Drop null user_id right here: an impression with no user cannot belong to any pair. #### 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 saw, where each count comes from a small helper set of per-user campaign totals. Round to two decimals for the dashboard. --- ### The solution **Self-join for pairwise campaign overlap** ```sql WITH user_campaigns AS ( SELECT DISTINCT user_id, ad_campaign FROM ad_impressions WHERE user_id 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 ``` > **Cost analysis** > > The distinct step shrinks 400M rows to roughly 3.75M memberships (15M users across 250 campaigns). The self-join is the real cost: a hot campaign seen by thousands of users produces O(n^2) pairs for that campaign alone. In production you cap this to active users, sample, or reach for MinHash. > **Interviewers watch for** > > The a.user_id < b.user_id guard. It is the tell that a candidate has reasoned about pair symmetry and self-pairs, instead of joining blindly and trying to divide the row count by two afterward. > **Common pitfall** > > Dividing by one user's set alone instead of the union. Jaccard measures overlap relative to everything either user saw, so the denominator is count_a + count_b - shared. Dividing by just the smaller set gives containment similarity, a different metric with different values. > **In production** > > This exact pairwise Jaccard powers 'users like you' recommendations and near-duplicate detection. At 15M users the full self-join is infeasible, so teams approximate it with MinHash or LSH, which estimate Jaccard without materializing every pair. --- ## 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 only wanted overlap among campaigns users actually clicked? _(The query counts all impressions regardless of click status; filtering to clicked-only would change the semantics.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_space_between_us) - [SQL Interview Questions](https://datadriven.io/sql-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.