Google: Search Experiment Lift Without Contaminated Users
A Search experiment splits users into a control arm and treatment arms.
- Difficulty: Hard
- Topics: Subqueries, Aggregation, Conditional Logic, Joins
- Dialect: MySQL
- Problem: #697
Problem statement
A Search experiment splits users into a control arm and treatment arms. A logging bug put some users in more than one arm; they are contaminated and must be dropped from every arm. A user can also have duplicate rows for the same arm — then only their earliest assigned_at counts.
A clean user converted if they have at least one conversion at or after their assignment time. For each arm with at least one clean user, return arm, users, converters, conversion_pct = 100 × converters ÷ users rounded to 2 decimals, and lift_pts = the arm's conversion_pct minus the control arm's conversion_pct (rounded to 2 decimals; NULL for the control arm itself and whenever control has no clean users). Order by arm.
A practice scenario set at Google: the tables and data are invented, and this is not a question from, or endorsed by, Google.
Tables
Table: ExperimentAssignment
| Column | Type |
|---|---|
| assignment_id | int |
| user_id | int |
| arm | enum(control, treatment_a, treatment_b) |
| assigned_at | datetime |
Primary key: assignment_id.
One assignment log row; a user may appear more than once.
Table: SearchConversion
| Column | Type |
|---|---|
| conversion_id | int |
| user_id | int |
| converted_at | datetime |
Primary key: conversion_id.
One conversion event (for example a sign-up started from a search); a user may convert several times.
Examples
Example 1
ExperimentAssignment
| assignment_id | user_id | arm | assigned_at |
|---|---|---|---|
| 1 | 1 | control | 2025-06-01 10:00:00 |
| 2 | 2 | control | 2025-06-01 11:00:00 |
| 3 | 3 | control | 2025-06-02 09:00:00 |
| 4 | 4 | treatment_a | 2025-06-01 09:00:00 |
| 5 | 5 | treatment_a | 2025-06-01 12:00:00 |
| 6 | 6 | treatment_a | 2025-06-02 12:00:00 |
| 7 | 6 | control | 2025-06-03 12:00:00 |
| 8 | 7 | treatment_b | 2025-06-01 15:00:00 |
| 9 | 8 | treatment_b | 2025-06-02 09:00:00 |
| 10 | 8 | treatment_b | 2025-06-04 09:00:00 |
SearchConversion
| conversion_id | user_id | converted_at |
|---|---|---|
| 1 | 1 | 2025-06-05 10:00:00 |
| 2 | 2 | 2025-05-30 18:00:00 |
| 3 | 4 | 2025-06-01 09:00:00 |
| 4 | 5 | 2025-06-03 12:00:00 |
| 5 | 5 | 2025-06-04 12:00:00 |
| 6 | 6 | 2025-06-05 09:00:00 |
| 7 | 8 | 2025-06-03 09:00:00 |
Output
| arm | users | converters | conversion_pct | lift_pts |
|---|---|---|---|---|
| control | 3 | 1 | 33.33 | NULL |
| treatment_a | 2 | 2 | 100 | 66.67 |
| treatment_b | 2 | 1 | 50 | 16.67 |
How to solve Google: Search Experiment Lift Without Contaminated Users
The assignment log has to be cleaned per user before any arm is measured. Grouping it by user_id and keeping COUNT(DISTINCT arm) = 1 drops every contaminated user from every arm at once — filtering per arm would wrongly keep them in each. For the survivors MIN(arm) is their one arm and MIN(assigned_at) their earliest assignment, which handles duplicate rows.
A user converted if some conversion happened at or after that time; EXISTS asks exactly that and counts a user once however many times they converted, and a conversion before assignment (organic, not caused by the experiment) is ignored. Grouping the flagged users by arm gives users, converters and the rounded rate.
Lift is a comparison across rows: each arm's rate minus control's. A scalar subquery reads control's rate; if control has no clean users it returns NULL and the difference is NULL, as required. The alternative cleans with MIN(arm) = MAX(arm), counts converters with COUNT(DISTINCT s.user_id) over a LEFT JOIN, and reads control by joining the control row. Both are a few grouped scans.
Reference solution (MySQL)
WITH clean AS (
SELECT user_id, MIN(arm) AS arm, MIN(assigned_at) AS assigned_at
FROM ExperimentAssignment
GROUP BY user_id
HAVING COUNT(DISTINCT arm) = 1
), flagged AS (
SELECT c.arm, c.user_id,
CASE WHEN EXISTS (SELECT 1 FROM SearchConversion s
WHERE s.user_id = c.user_id AND s.converted_at >= c.assigned_at)
THEN 1 ELSE 0 END AS converted
FROM clean c
), arms AS (
SELECT arm, COUNT(*) AS users, SUM(converted) AS converters,
ROUND(100 * SUM(converted) / COUNT(*), 2) AS conversion_pct
FROM flagged
GROUP BY arm
)
SELECT a.arm, a.users, a.converters, a.conversion_pct,
CASE WHEN a.arm = 'control' THEN NULL
ELSE ROUND(a.conversion_pct - (SELECT conversion_pct FROM arms WHERE arm = 'control'), 2)
END AS lift_pts
FROM arms a
ORDER BY a.armAnother way
WITH firsts AS (SELECT user_id, MIN(arm) AS arm, MAX(arm) AS other_arm, MIN(assigned_at) AS assigned_at FROM ExperimentAssignment GROUP BY user_id), arms AS (SELECT f.arm, COUNT(DISTINCT f.user_id) AS users, COUNT(DISTINCT s.user_id) AS converters FROM firsts f LEFT JOIN SearchConversion s ON s.user_id = f.user_id AND s.converted_at >= f.assigned_at WHERE f.arm = f.other_arm GROUP BY f.arm), pct AS (SELECT arm, users, converters, ROUND(100 * converters / users, 2) AS conversion_pct FROM arms) SELECT p.arm, p.users, p.converters, p.conversion_pct, IF(p.arm = 'control', NULL, ROUND(p.conversion_pct - ctl.conversion_pct, 2)) AS lift_pts FROM pct p LEFT JOIN pct ctl ON ctl.arm = 'control' ORDER BY p.arm← Google: Median First-Reply Time in Gmail Support Threads · Hotstar: Death-Over Ad Breaks Running Long →