Match a Product Variant from Selected Options

Updated · By

Index every in-stock variant by option value, then intersect: a value is available when some in-stock variant carries it together with every other current selection, ignoring that option's own selection. Resolve the chosen variant with one hash lookup on the full selection. Build the index once per product; each click is then set intersections.

mediumPattern: Arrays and hashingFrom Devana's Shopify question set

Problem

A product has options such as color and size. Each combination that is actually made is a variant with its own id, price and stock count. A shopper picks values one option at a time, and after every click the product page has to answer two questions.

First, which variant has the shopper chosen? That is only defined once every option has a value and a variant with exactly those values exists. Second, which values of each option can still be picked? A value is offered when some in-stock variant carries it alongside everything else currently selected.

Write resolve_variant(variants, selected). Each variant is a dict with id, options (option name to value), price and stock. selected maps option names to values and may be partial. Return the matched variant id, or None, and for every option the values still available, sorted.

def resolve_variant(variants: list[dict], selected: dict) -> dict:
    """Return {"variant": id or None, "available": {option: [values]}}."""

This is one of Devana's own questions, written in the style of Shopify's interviews. It is not a question leaked from Shopify, and Devana is not affiliated with Shopify.

Constraints

  • An option's own selection is ignored when computing its availability, so the shopper can always switch it to another value.
  • A variant with stock of 0 exists but cannot be bought, so it never makes a value available.
  • A variant is resolved only when every option is selected and a variant with exactly those values exists.
  • Available values are sorted ascending; an option with nothing available gets an empty list.
  • Assume a few options and up to a few hundred variants; a follow-up asks about thousands.

Examples

Example 1

Input:  variants = red/S (stock 3), red/M (stock 0), red/L (stock 1)
        selected = {"color": "red"}
Output: {"variant": None, "available": {"color": ["red"], "size": ["L", "S"]}}

M is made but sold out, so it is not offered. Size is not chosen yet, so no variant is resolved.

Example 2

Input:  variants = red/S (stock 3), blue/M (stock 2)
        selected = {"color": "blue", "size": "S"}
Output: {"variant": None, "available": {"color": ["red"], "size": ["M"]}}

Nobody makes a blue S. Color still offers red, because red comes in S, and size offers M, the only size made in blue. Each list ignores its own option's selection, which is what gets the shopper out of the dead end.

Hints

Open one at a time, and try the problem again after each.

Hint 1

Answer the two questions separately. Resolving the variant is a lookup; availability is a filter.

Hint 2

For one option, drop its own selection, then ask which in-stock variants match everything that is left. The values those variants carry for this option are the available ones.

Hint 3

Precompute, for each option and value, the set of in-stock variant ids that carry it. Matching several selections is then a set intersection rather than a scan.

Hint 4

For resolution, key each variant by its sorted (option, value) pairs in a dict, so a full selection is one lookup whatever order it was clicked in.

Approach: from brute force to optimal

Brute force: rescan the variants for every option

For each option, loop over every variant, check it is in stock, check it matches every other selection, and collect its value for this option. Resolve the variant with one more scan comparing all options. It is correct and easy to explain, and it redoes the same matching work on every click.

Complexity: O(o² × v) per click for o options and v variants; O(v) extra space

Index by option value, then intersect

Build carrying[option][value], the set of in-stock variant ids with that value, in one pass when the product loads. For an option, start from all in-stock ids and intersect the sets for each other selection. A value is available if its own set shares an id with the result.

Resolution uses a dict keyed by each variant's sorted (option, value) pairs, built in the same pass, so a full selection resolves in O(o). The worst case per click is no better than the scan, but the work now shrinks with the matching sets instead of always touching every variant, and the index is built once rather than per click.

Complexity: O(o × v) time and space to build once; per click, intersections over sets of at most v ids

Bitsets when there are thousands of variants

Number the variants and store each set as a bitmask. An intersection becomes a bitwise AND over v/64 machine words, and checking whether a value is available is one more AND and a test for zero.

Complexity: O(o² × v / 64) word operations per click

How to say it in the interview

Say the two outputs first, and the rule that makes availability subtle: each option ignores its own selection. Then: "I will precompute which in-stock variants carry each value, once per product. Per click, availability is an intersection of those sets, and the variant is one dict lookup on the full selection." Mention that a sold-out variant still exists for resolution but never makes a value available, so the interviewer hears that you read the constraints.

Solution

Python

def resolve_variant(variants, selected):
    names = sorted({name for v in variants for name in v["options"]})

    # carrying[name][value]: ids of in-stock variants with that value.
    carrying = {name: {} for name in names}
    in_stock, by_key = set(), {}
    for v in variants:
        by_key.setdefault(tuple(sorted(v["options"].items())), v["id"])
        if v["stock"] > 0:
            in_stock.add(v["id"])
            for name, value in v["options"].items():
                carrying[name].setdefault(value, set()).add(v["id"])

    available = {}
    for name in names:
        # Ignore this option's own selection, so it can always be changed.
        ids = set(in_stock)
        for other, value in selected.items():
            if other != name:
                ids &= carrying.get(other, {}).get(value, set())
        available[name] = sorted(
            value for value, have in carrying[name].items() if have & ids
        )

    variant = None
    if names and all(name in selected for name in names):
        variant = by_key.get(tuple(sorted(selected.items())))
    return {"variant": variant, "available": available}

JavaScript

function resolveVariant(variants, selected) {
  const names = [...new Set(variants.flatMap((v) => Object.keys(v.options)))].sort();
  const keyOf = (options) => JSON.stringify(Object.entries(options).sort(([a], [b]) => (a < b ? -1 : a > b ? 1 : 0)));

  // carrying: name -> value -> ids of in-stock variants with that value.
  const carrying = new Map(names.map((name) => [name, new Map()]));
  const inStock = new Set();
  const byKey = new Map();
  for (const v of variants) {
    if (!byKey.has(keyOf(v.options))) byKey.set(keyOf(v.options), v.id);
    if (v.stock <= 0) continue;
    inStock.add(v.id);
    for (const [name, value] of Object.entries(v.options)) {
      const values = carrying.get(name);
      if (!values.has(value)) values.set(value, new Set());
      values.get(value).add(v.id);
    }
  }

  const available = {};
  for (const name of names) {
    // Ignore this option's own selection, so it can always be changed.
    let ids = [...inStock];
    for (const [other, value] of Object.entries(selected)) {
      if (other === name) continue;
      const have = carrying.get(other)?.get(value) ?? new Set();
      ids = ids.filter((id) => have.has(id));
    }
    available[name] = [...carrying.get(name)]
      .filter(([, have]) => ids.some((id) => have.has(id)))
      .map(([value]) => value)
      .sort();
  }

  const complete = names.length > 0 && names.every((name) => Object.hasOwn(selected, name));
  return { variant: complete ? byKey.get(keyOf(selected)) ?? null : null, available };
}

Both versions are tested against the same cases, including every example on this page.

  • A sold-out variant still resolves when every option is chosen, so the page can say "sold out" for that exact combination. It never makes a value available.
  • The lookup key is the sorted (option, value) pairs, so the order the shopper clicked in does not matter.
  • An empty selection returns every value some in-stock variant carries, and no variant.

Follow-up questions

How do you compute availability for a partial selection efficiently?

With the intersections above: precompute the in-stock id sets per value once, and each click intersects at most one set per selected option. With many variants, bitsets make each intersection a handful of word operations.

What do you do when the selected combination does not exist?

Return no variant, keep every option's availability, and let the page suggest the nearest valid change. Because each option ignores its own selection, the lists already show the way out.

How do you handle a product with a thousand variants?

Build the index when the product loads, not per click, and switch the id sets to bitmasks. A thousand variants is 16 words of 64 bits per mask.

How do you keep this correct as stock changes during the session?

Treat the page's answer as a hint. Refresh stock on an interval or a push, rebuild the affected sets, and check stock again at add-to-cart and at checkout, which is where it has to be exact.

Common mistakes

  • Applying an option's own selection when computing its availability. Choosing red then shows red as the only color and the shopper can never switch.
  • Letting a zero-stock variant make its values available.
  • Resolving a variant from a partial selection because only one variant happens to match so far.
  • Comparing option dicts in insertion order, so color-then-size and size-then-color look different.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview