Where the Bill Settles

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

City and County of San Francisco

Problem

We're reviewing spend across our US regions, where every cloud charge sits as one row in cloud_costs tagged with its service and the amount billed. A handful of enormous bills drag the average up, so for each service we track the median charge instead. Looking only at charges in the us-east-1, us-west-2, and us-central1 regions, return the five services with the highest median, largest first.

When a handful of giant charges skew the average, the middle tells the truth.

Tables

cloud_costs

Columns: cost_id INTEGER, provider TEXT, svc_name TEXT, region TEXT, amount REAL, acct_id TEXT, bill_date TEXT

Expected output

Worked solution and explanation

What this really is

Strip the cloud-billing costume and this is 'find the middle value of each group' in an engine with no median function. The US-region filter and the five-service cut are the easy bookends; the median in the middle is what separates candidates. The tell: do you pick ONE middle row (wrong for even counts) or AVERAGE the two central values? Pick one middle row and every service with an even number of charges reports a median off by half the gap between its two central bills, and the highest-to-lowest ordering (and therefore which five make the cut) shifts with it.

There is no PERCENTILE_CONT here, so the portable move is the rank-window pattern: ROW_NUMBER over the partition, COUNT over the partition, then average every row whose position sits in the middle band. The robust way to express that band is integer-only, 2 * rn between cnt and cnt + 2, which keeps one row for odd counts and the two central rows for even ones with no division rounding to trip over.

Break down the requirements

Step 1: Scope to the US regions, then tag every row with its rank and partition size

Filter to region IN ('us-east-1', 'us-west-2', 'us-central1') FIRST, in a CTE, so only in-scope charges reach the windows. Do the filter after ranking and every partition is polluted by non-US charges and the medians are wrong. Inside the filtered set, ROW_NUMBER() OVER (PARTITION BY svc_name ORDER BY amount) gives a 1-indexed position within each service, and COUNT(*) OVER (PARTITION BY svc_name) attaches the partition total to every row, so the middle-band test has its group size without a self join.

Step 2: Select the middle band with 2 * rn

The condition 2 * rn >= cnt AND 2 * rn <= cnt + 2 is pure integer arithmetic, so it does not depend on whether the engine treats / as integer or float division. For odd cnt it isolates the single middle row; for even cnt it keeps both central rows. This is where the naive rn = (cnt+1)/2 test quietly breaks: on an engine that evaluates that division as a float, the x.5 position for even counts matches no integer rank and you silently keep only the upper-middle row.

Step 3: Average the picked rows per service, then take the top five

The WHERE keeps one or two rows per svc_name. AVG(amount) GROUP BY svc_name averages whatever it kept, giving the true median for either parity. ORDER BY median_amount DESC then svc_name ASC gives the highest-first ordering with the alphabetical tie break, and LIMIT 5 takes the five services with the largest medians.

The solution

WITH us_charges AS (
  SELECT svc_name, amount
  FROM cloud_costs
  WHERE region IN ('us-east-1', 'us-west-2', 'us-central1')
),
ranked AS (
  SELECT svc_name, amount,
         ROW_NUMBER() OVER (PARTITION BY svc_name ORDER BY amount) AS rn,
         COUNT(*) OVER (PARTITION BY svc_name) AS cnt
  FROM us_charges
)
SELECT svc_name, AVG(amount) AS median_amount
FROM ranked
WHERE 2 * rn >= cnt AND 2 * rn <= cnt + 2
GROUP BY svc_name
ORDER BY median_amount DESC, svc_name ASC
LIMIT 5

Common follow-up questions

• Walk through why 2 * rn between cnt and cnt + 2 selects one middle row for odd counts and both middle rows for even counts. (Tests algorithm understanding. cnt=5 keeps rn=3 only; cnt=4 keeps rn=2 and rn=3. Because the band is integer-only there is no rounding to reason about, which is exactly why it is safe across engines.)
• How would you compute the 90th percentile instead? (Tests pattern generalization. Keep the same windowing and target the position near 0.9 * cnt rather than the center; for a single interpolated value you scale the rank offset instead of picking a symmetric middle band.)
• Why not use NTILE(2) and pick the boundary? (Tests awareness of NTILE semantics. NTILE distributes rows into N buckets but does not guarantee the boundary row is the median; for small partitions the boundary diverges from the true middle value.)