Google's marketing team is making a report on how many searches users handle. Write a query to report the median of searches made by users.
This is one of Google's most challenging SQL problems, testing your understanding of statistical calculations in SQL and recursive CTEs. Calculating medians in SQL is notoriously tricky because SQL is designed for set operations, not ordered statistics. Google uses this to assess candidates' ability to handle complex analytical queries that go beyond simple aggregations—essential for their massive-scale data analysis infrastructure.
Advanced concepts tested: recursive CTEs for data expansion, ROW_NUMBER() window function for ordering, COUNT() OVER() for total row calculation, FLOOR() and CEIL() for median position logic, and understanding frequency tables where one row represents multiple data points. This problem requires transforming aggregated data back into individual rows before calculating the median.
Google's data scientists use median calculations extensively to: analyze search query distributions while being robust to outliers, calculate typical page load times across billions of requests, measure user engagement metrics that aren't skewed by power users, generate percentile-based SLAs for infrastructure monitoring, and create fair comparison metrics across different user segments in A/B tests.
When tackling this Google problem, the key is to understand the grain of the result. Are you returning one row per user, or one row per category? Always start by identifying your unique join keys and consider if filtered aggregations (CASE WHEN) are more efficient than multiple subqueries.
Be careful with NULL values in your JOIN conditions or aggregate functions. In interview scenarios, datasets often include edge cases like zero-count categories or duplicate entries that can throw off a simple COUNT(*) if not handled with DISTINCT.
Share your approach, optimized queries, or ask questions. Learning from others is the fastest way to master SQL.
WITH RECURSIVE expanded AS (
SELECT searches, num_users
FROM search_frequency
UNION ALL
SELECT searches, num_users - 1
FROM expanded
WHERE num_users > 1
),
ranked AS (
SELECT
searches,
ROW_NUMBER() OVER (ORDER BY searches) AS rn,
COUNT(*) OVER () AS total
FROM expanded
)
SELECT ROUND(AVG(searches), 1) AS median
FROM ranked
WHERE rn IN (
FLOOR((total + 1) / 2.0),
CEIL((total + 1) / 2.0)
);The recursive CTE expands each frequency row into individual synthetic rows — one per user — effectively recreating the raw dataset. ROW_NUMBER then assigns a position to each expanded row, and total captures the full count. The median is the middle value for odd totals or the average of the two middle values for even totals, selected by the FLOOR/CEIL formula. This approach is the most explicit: every user is represented once. The downside is memory usage — if total users is very large (millions), expanding the table is expensive. It is best suited for moderate-sized datasets.
WITH cumulative AS (
SELECT
searches,
SUM(num_users) OVER (ORDER BY searches) AS cum_users,
SUM(num_users) OVER (ORDER BY searches) - num_users AS prev_cum,
SUM(num_users) OVER () AS total
FROM search_frequency
)
SELECT ROUND(AVG(searches), 1) AS median
FROM cumulative
WHERE
prev_cum < (total + 1) / 2.0
AND cum_users >= (total + 1) / 2.0;Instead of expanding rows, this approach computes cumulative user counts using window functions over the compact frequency table. A search bucket contains the median when the cumulative count crosses the midpoint — i.e., the previous cumulative total is below the midpoint but the current one meets or exceeds it. For even totals, the midpoint may fall between two buckets, and the WHERE clause catches both. No recursion or row explosion occurs, so this runs efficiently even when total users numbers in the millions. It is the preferred production solution but requires careful reasoning about boundary conditions.
The recursive CTE expansion approach creates a virtual table with one row per user, so its memory and compute cost scales linearly with the total number of users across all search frequency buckets. If search_frequency has 100 rows but represents 10 million total users, the recursive CTE generates 10 million virtual rows before applying window functions — potentially exceeding memory limits or hitting recursion depth limits in databases like MySQL (which has a default cte_max_recursion_depth of 1000). The cumulative window function approach operates only on the compact frequency table — typically tens to hundreds of rows — making it orders of magnitude cheaper at scale. A simple index on search_frequency(searches) helps the ORDER BY in the window functions avoid a sort step. For this specific problem, the compact table is almost always small enough that either approach runs instantly, but understanding the trade-off is what interviewers are testing.
The most subtle mistake is using integer division instead of float division in the median index formula: FLOOR((total + 1) / 2) in SQL may perform integer division in some dialects, shifting the result. Using (total + 1) / 2.0 or CAST ensures floating-point arithmetic. Candidates also commonly select only the lower-middle row for even totals, forgetting to average two values when total is even. Another pitfall with the recursive approach is forgetting the base case or the termination condition (num_users > 1), causing infinite recursion. With the cumulative approach, the off-by-one boundary condition — using > vs >= for the cumulative thresholds — frequently produces wrong results on even-total edge cases.
Storing one row per user would require a table with potentially millions of rows for a simple integer frequency distribution. A frequency table (searches, num_users) is a compact aggregate representation that is common in analytics and data warehousing contexts. The problem tests whether you can work with pre-aggregated data — a more realistic scenario than raw logs — and whether you understand that statistical computations like median require either expanding the data back to individual observations or reasoning about cumulative distributions directly.
You can use a self-join approach: compute total users, then join the frequency table against itself where the cumulative sum of one side crosses the midpoint. Alternatively, in databases that support PERCENTILE_CONT or PERCENTILE_DISC ordered-set aggregate functions (PostgreSQL, SQL Server, BigQuery), you can expand the table once with a CROSS JOIN GENERATE_SERIES and call PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY searches). However, these approaches are either more verbose or database-specific.
Partition the window functions by the grouping column. In the cumulative approach, add a PARTITION BY category clause to all SUM() OVER() expressions so cumulative counts reset for each group. In the recursive approach, include category in the recursive CTE and in the ROW_NUMBER partition. The FLOOR/CEIL median formula applies independently within each partition. This extension is a natural follow-up interviewers use to test whether you understand PARTITION BY vs global window frames.