Three-Value Sum Combinations

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

Asked in

Lyft

Problem

Find all combinations of 3 different employee metric records whose values sum to exactly 25. Each combination must use three separate records with no reuse. Show the three values in each qualifying combination.

Pick three. See what they add up to.

Tables

employee_metrics

Columns: metric_id INTEGER, department TEXT, metric_name TEXT, metric_value REAL, fiscal_quarter TEXT, fiscal_year INTEGER

Expected output

Worked solution and explanation

The mental model: k-combinations as a self-join

This is identity-based combination counting dressed up as a metrics puzzle. Anyone can chain three copies of employee_metrics; what separates candidates is which column keeps the copies apart. Chain them on metric_id and every group of three records comes back exactly once, equal values included. Order or dedupe on metric_value instead and you quietly drop triples like 8.8 + 8.1 + 8.1, where two different records share a value, or collapse the record triples that repeat the same numbers. Either way the row count no longer matches.

The three traps

Step 1: No-reuse is not the same as no-duplicate-output

Beginners reach for e1.metric_id != e2.metric_id AND e2.metric_id != e3.metric_id AND e1.metric_id != e3.metric_id. That correctly enforces three separate records, but each underlying combination still surfaces six times, once per permutation (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). The strict inequality chain e1.metric_id < e2.metric_id AND e2.metric_id < e3.metric_id collapses all six permutations into the single canonical ascending ordering, so dedup is built into the join itself rather than bolted on with DISTINCT.

Step 2: Cartesian product cost explosion

Three copies of a 10,000-row table is 10^12 = 1 trillion tuples before any filter. The ascending-id chain keeps one ordering of each triple, roughly 167 billion, but an inequality cannot drive a hash join, so the engine still walks it as nested loops. On the 200-row seed that is C(200,3) = 1,313,400 triples and returns instantly; at 10,000 rows it stops being interactive. At that scale you would NOT reach for this pattern; you would precompute pair sums into an indexed table and look up the complement 25 - pair_sum instead.

Step 3: Order by a unique key, never by the value you are summing

The inequality must reference a column that is unique per row, and metric_id is unique on every record. If you wrote e1.metric_value < e2.metric_value AND e2.metric_value < e3.metric_value thinking it accomplished the same dedup, the strict < silently drops every triple where two records share a value. On this seed every value sits on two records, so 8.8 + 8.1 + 8.1 is a real answer and it vanishes. Combinatorics dedup is a property of row identity, not row payload.

The solution

SELECT e1.metric_value AS val1,
       e2.metric_value AS val2,
       e3.metric_value AS val3
FROM employee_metrics e1
CROSS JOIN employee_metrics e2
CROSS JOIN employee_metrics e3
WHERE e1.metric_id < e2.metric_id
  AND e2.metric_id < e3.metric_id
  AND e1.metric_value + e2.metric_value + e3.metric_value = 25

Common follow-up questions

• If two `employee_metrics` rows have identical `metric_value`, do they both qualify as 'different records' for this prompt? (Tests whether you understand the dedup is keyed on row identity (`metric_id`), not value equality. The answer is yes, they are distinct records.)
• How many output rows do you get if you write `e1.metric_id != e2.metric_id AND e2.metric_id != e3.metric_id AND e1.metric_id != e3.metric_id` instead of the strict-inequality chain? (Probes whether you can articulate the 6x permutation inflation and the distinction between distinctness and canonical ordering.)
• Rewrite this for combinations of 4 records summing to 50. How many self-joins, and how long is the inequality chain? (Generalizes the pattern: K self-joins, K-1 inequalities, and the sum predicate now has 4 terms. Also a setup for asking about the O(N^4) cost.)
• At 100k records this query takes hours. What algorithm would you switch to? (Looking for hash-the-complement (precompute pair sums into a lookup table, probe for `25 - pair`) or sort plus two-pointer. Either drops the complexity by an order of magnitude.)
• What if `metric_value` can be negative? Does the query still produce correct results? (Yes, the predicate `sum = 25` works fine with negatives. This is a probe to check you are not unconsciously assuming positivity (some candidates add `metric_value > 0` for no reason).)