Loaded Dice

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

Goldman Sachs

Problem

Some flags never seem to win in the experimentation team's weighted picker, which treats each flag's rollout in feat_flags as its weight and skips flags with no rollout set. For every candidate, report its share of the total rollout and its running share accumulated from the smallest rollout up, equal rollouts taken in flag_id order. The picker draws a whole-number ticket from 0 to 9,999, so also give the ticket band each flag owns: where its running share starts and where it ends, in whole basis points rounded down.

Every flag's rollout is a bet. Map the odds from longest shot to favorite.

Tables

feat_flags

Columns: flag_id INTEGER, flag_name TEXT, rollout REAL, enabled INTEGER, owner TEXT, created TEXT, updated TEXT

Expected output

Worked solution and explanation

What this really is

This is a cumulative distribution function dressed up as a feature-flag picker. Two sums ride over the same filtered rows: a whole-set SUM(rollout) OVER () as the shared denominator, and a running SUM(rollout) walked from the smallest weight up. Everyone writes the running sum. What separates candidates is the frame. rollout is heavily skewed, so ties are guaranteed (flags 1774 and 10003254 both sit at 2.0), and the default frame treats peers as one step. Leave it implicit and both tied flags get the same cumulative value: a zero-width band one of them can never win. That is exactly the symptom in the prompt, and you just reproduced the bug instead of fixing it.

Build it in four moves

Step 1: Keep only the candidates

Filter with rollout IS NOT NULL before any window runs. Sixty percent of the table has no rollout, and those flags must vanish from the total as well as the output, or every share comes out short of its true value.

Step 2: Attach the grand total to every row

SUM(rollout) OVER () with nothing inside the parentheses is the total across every surviving flag, attached to each row. Dividing rollout by it gives probability, and those shares sum to exactly 1.

Step 3: Accumulate the shares row by row

A second window sums rollout ordered by rollout, flag_id over a ROWS frame, then divides by the same total. The last row lands exactly on 1, and each tied flag climbs past its twin.

Step 4: Cut each band into ticket_floor and ticket_ceiling

The ceiling is the running sum including this flag, scaled by 10000 over the total. The floor is the same running sum minus the flag's own rollout, so the first flag starts at 0 and every floor equals its predecessor's ceiling. Wrap each edge in CAST(... AS INTEGER) so both land on a whole ticket.

The solution

SELECT
    flag_id,
    flag_name,
    rollout,
    rollout / SUM(rollout) OVER () AS probability,
    SUM(rollout) OVER (
        ORDER BY rollout, flag_id
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) / SUM(rollout) OVER () AS cumulative_prob,
    CAST(
        (SUM(rollout) OVER (
            ORDER BY rollout, flag_id
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) - rollout) * 10000 / SUM(rollout) OVER ()
    AS INTEGER) AS ticket_floor,
    CAST(
        SUM(rollout) OVER (
            ORDER BY rollout, flag_id
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) * 10000 / SUM(rollout) OVER ()
    AS INTEGER) AS ticket_ceiling
FROM feat_flags
WHERE rollout IS NOT NULL

Implicit frame

SUM(rollout) OVER (ORDER BY rollout) defaults to a RANGE frame. Flags 1774 and 10003254 both read 0.001191, so both bands run from 0 to 11 and the draw cannot tell them apart.

Explicit ROWS frame

ORDER BY rollout, flag_id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW gives 0.000596 then 0.001191: bands 0 to 5 and 5 to 11. Each tied flag owns its own slice of the draw.

Common follow-up questions

• Given a ticket from 0 to 9,999, how do you pick the winning flag? (Return the flag whose `ticket_floor` is at most the ticket and whose `ticket_ceiling` is above it.)
• What happens to a flag whose share is below one basis point? (Tiny rollouts can truncate to the same floor and ceiling, leaving a zero-width band even with the tie fixed.)
• What is the difference between a flag with `rollout` 0 and one with no rollout set? (Tests whether the candidate separates a real candidate with zero weight from a flag excluded by `rollout IS NOT NULL`.)