# The Costliest Trio > Three products, one price tag. Surface the priciest bundles. Canonical URL: Domain: SQL · Difficulty: medium · Seniority: L4 ## Problem We're building a gift-bundle recommender for a retail catalog, where every bundle is three different products and its price is the sum of the three item costs. Surface the 100 most expensive bundles, listing each bundle's three product names alphabetically in one comma-separated string next to its combined price. ## Worked solution and explanation ### What this is really testing This is the classic unordered-triple problem wearing a retail costume, with a scale trap sewn into the lining. Two skills are being probed at once. First: can you generate every unique 3-item set exactly once, instead of emitting the same trio six times in shuffled order? The strict inequality chain a.product_name < b.product_name < c.product_name collapses all six permutations of a trio into the single one already in alphabetical order, and hands you the names pre-sorted for the concatenation. Second, and this is what separates candidates: do you notice that a blind three-way self-join over the whole catalog is O(N^3)? A few thousand products is billions of triples. Write it naively and the sorter tries to materialize the cross product on disk and the query dies with a disk I/O error before it ever returns a row. > **Trick to solving** > > The 100 priciest bundles can only be built from the priciest products. So prune first: take the top few hundred rows by price in a CTE, then run the three-way self-join over that tiny set. You get the exact same top 100, on a join that fits in memory. --- ### Building it up #### Step 1: Prune to the priciest products In a CTE, keep only the priciest products: ORDER BY price DESC LIMIT 200 (and drop NULL prices while you are here). Why 200 is safe for a top-100: pair the two most expensive items with each of the next 198, and you already have 198 bundles that beat any bundle reaching past rank 200. So the true top 100 never leaves the top 200, and the O(N^3) join shrinks from N=5000 to N=200. #### Step 2: Set up the three-way self-join Alias the pruned set three times (a, b, c) and join with the chain a.product_name < b.product_name < c.product_name. This emits each unordered 3-item set exactly once, and because the chain follows lexicographic order, the three names already arrive alphabetically with no extra sorting inside the row. #### Step 3: Concatenate, score, order, and bound Build the combo with a.product_name || ',' || b.product_name || ',' || c.product_name, sum the three prices as total_cost, order by total_cost descending with the combo string ascending as the tie-breaker, and cap at LIMIT 100. --- ### The solution **Prune first, then self-join with an inequality chain** ```sql WITH ranked AS ( SELECT product_name, price FROM products WHERE price IS NOT NULL ORDER BY price DESC LIMIT 200 ) SELECT a.product_name || ',' || b.product_name || ',' || c.product_name AS combo, a.price + b.price + c.price AS total_cost FROM ranked a JOIN ranked b ON a.product_name < b.product_name JOIN ranked c ON b.product_name < c.product_name ORDER BY total_cost DESC, combo ASC LIMIT 100 ``` > **Why pruning, not the LIMIT, is what saves you** > > The count of 3-combinations from N items is N*(N-1)*(N-2)/6, which grows cubically. At 5000 products that is over 20 billion triples, and no LIMIT saves you, because the sorter still has to see every triple before it can pick the top 100. Pruning to the top 200 turns that into about 1.3 million triples, roughly a 15,000x reduction, and the final ORDER BY ... LIMIT 100 keeps only a bounded 100-row heap. That is the difference between a disk spill and a query that returns instantly. > **Common pitfall** > > Reaching for an id to order the join instead of the name. If you write the chain on some product_id (a.id < b.id < c.id), you still get each trio once, but the three names come out in id order, not alphabetical order, so the combo string is wrong. The requirement is an alphabetical combo, so the ordering constraint has to be on product_name itself. Chaining the inequality on the name does the dedup AND the alphabetization in one move. > **Interviewers watch for** > > Interviewers watch for whether you clock the combinatorial explosion before you hit run. A strong candidate asks about catalog size, realizes a full three-way self-join is O(N^3), and reaches for the prune-then-combine shape rather than trying to enumerate every triple. **Naive: self-join the whole catalog** Three aliases over all 5000 rows. About 20 billion triples materialized before the sort can begin. The sorter spills to disk and the query dies with a disk I/O error, having returned nothing. **Pruned: self-join the top 200** A CTE keeps the 200 priciest rows, then the same three-way join runs over those. About 1.3 million triples, an in-memory sort, an identical top 100, and it returns immediately. --- ## Common follow-up questions - What changes if you need 4-item bundles instead of 3? _(Tests extending the inequality chain to a fourth alias with a.name < b.name < c.name < d.name, and re-checking the safe prune size.)_ - How would you restrict bundles to products in the same category? _(Tests adding an equality predicate on category to each join condition.)_ - How do you choose the LIMIT in the CTE, and how do you know it never drops a bundle that belongs in the top 100? _(Probes the safety argument for the prune size and how it scales with the requested top-K.)_ - Why is LIMIT 100 alone not enough to keep this query from spilling to disk? _(Tests understanding that a plain LIMIT bounds only the final heap, not the number of triples the sorter must scan.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_costliest_trio) - [SQL Interview Questions](https://datadriven.io/sql-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.