The Costliest Trio

A medium SQL interview practice problem on DataDriven. Write the query and run it against a real database, with instant feedback.

Domain

SQL

Difficulty

medium

Seniority

L4

Problem

List the 100 cheapest gift bundles in the products catalog, cheapest first, where a bundle is three different products priced at the sum of their prices and labeled by their names in alphabetical order, joined with commas. A product with no listed price can't go into any bundle, and bundles at the same price are listed alphabetically by that label.

Three products, one price tag. Surface the priciest bundles.

Tables

products

Columns: product_name TEXT, price REAL, product_id INTEGER, category TEXT, rating REAL, in_stock INTEGER

Expected output

Worked solution and explanation

What this is really testing

This is the unordered-triple problem wearing a gift-shop costume. Everyone sees the self-join; what separates candidates is how the three copies are tied together and what happens to the rows with no price. Join with <> and every trio comes back six times under six different labels. Join on < over product_name and the six permutations collapse to the one already in alphabetical order, which is also the label you were asked for. Then the quiet trap: in a cheapest-first sort a NULL total lands ahead of every real price, so skip the missing-price filter and your list of bargains opens with bundles that have no price at all.

Building it up

Step 1: Drop unpriced products first

In a CTE called priced, keep product_name and price where price IS NOT NULL. A bundle needs three real prices, and filtering once here means all three aliases inherit it instead of you repeating the guard on each.

Step 2: Chain the three copies on the name

Alias priced as a, b and c, joining b on a.product_name < b.product_name and c on b.product_name < c.product_name. Transitivity gives you a < c for free, so no product pairs with itself and no trio repeats.

Step 3: Label, total, sort, cut

Build combo with || and commas, add the three prices into total_cost, sort by total_cost then combo, both ascending, and stop at LIMIT 100. The label as a second key matters exactly where equal totals straddle the cut.

The solution

WITH priced AS (
  SELECT product_name, price
  FROM products
  WHERE price IS NOT NULL
)
SELECT a.product_name || ',' || b.product_name || ',' || c.product_name AS combo,
       a.price + b.price + c.price AS total_cost
FROM priced a
JOIN priced b ON a.product_name < b.product_name
JOIN priced c ON b.product_name < c.product_name
ORDER BY total_cost ASC, combo ASC
LIMIT 100

Not-equal join

a.product_name <> b.product_name and so on keeps every permutation: each trio appears six times with six different combo strings, and the top 100 holds only about seventeen real bundles.

Strict less-than chain

a.product_name < b.product_name < c.product_name keeps one permutation per trio, the alphabetical one, so combo is already the label and the top 100 is 100 distinct bundles.

Common follow-up questions

• What changes for 4-item bundles? (Tests extending the chain to a fourth alias with `c.product_name < d.product_name`.)
• How would you restrict bundles to products in the same category? (Tests adding an equality on `category` to each join condition.)
• If you prune to the cheapest K products, how large must K be to never lose a top-100 bundle? (Probes the argument that pairing the two cheapest items with each of the next K items gives K bundles cheaper than any bundle reaching past them.)
• Would sorting with `NULLS LAST` be an acceptable replacement for the filter? (Tests whether the candidate sees that `NULLS LAST` hides the rows but does not make an unpriced bundle meaningful.)