skip to content

Why does `sku in stock_list` dominate a pick-list builder's runtime, and what does a set change?

level: seniorimportance: should knowfreq 60%

answer

  1. The operator dispatches to the container
  2. One structure scans, one jumps
  3. n times m becomes n plus m
  4. Hoist the conversion out of the loop
  5. A derived snapshot can go stale

basics

~20 s

Membership on a list is a linear scan that compares elements one by one, so checking many SKUs against a long list is quadratic overall. Membership on a set is a single hash lookup, constant time on average, turning the pass from O(n*m) into O(n+m) after one O(n) build.

solid answer

~50 s

`x in some_list` walks the list comparing with `__eq__` until it hits a match or the end - O(n) per test, so testing m order lines against n stock rows is O(n*m). `x in some_set` hashes `x` once and probes a single location: O(1) on average. Building the set costs one O(n) pass, which pays for itself as soon as you do more than a couple of lookups, so the fix is to build it once outside the loop - `if sku in set(stock)` inside the loop rebuilds it every iteration and changes nothing. The tradeoffs a senior names: the set costs extra memory per element on top of the objects themselves, it silently loses duplicate counts and order, its elements must be hashable, and it is a snapshot - if the source list is mutated afterwards, the set is a stale cached value and the pick list ships wrong.

code

python · 8 lines
python
import timeit

stock = [f'SKU-{n}' for n in range(20_000)]
stock_set = set(stock)

scan = timeit.timeit(lambda: 'SKU-19999' in stock, number=200)
hashed = timeit.timeit(lambda: 'SKU-19999' in stock_set, number=200)
print(f'list {scan:.4f}s   set {hashed:.6f}s')

go deeper

for a junior

Recall that in on a list checks elements one by one while in on a set is a single hash lookup, and that building a set from a list is a one-off linear pass.

for a middle

Explain the arithmetic - m lookups over n rows going from O(n*m) to O(n+m) - and spot the classic bug of calling set(...) inside the loop, which keeps the cost quadratic and adds hashing on top.

for a senior

Show the whole tradeoff in production terms: measure before switching, budget the extra memory, name what the set discards (counts, order, unhashable items), and treat the derived set as a snapshot with a lifetime rather than a permanent cache.

for a principal

Own the policy question of where derived indexes live and who invalidates them. Repeated ad-hoc sets scattered through a pipeline are a staleness surface; decide whether the index is built per pass, owned by one component, or pushed down to the data store instead.

## What `in` actually does on each type The `in` operator is not one algorithm; it dispatches to the container. On a `list`, `__contains__` walks the elements from index 0, testing `x is element or x == element`, and stops at the first hit. Average cost for a present element is n/2 comparisons, and a miss always costs the full n - which is the case that hurts, because a pick-list builder mostly asks about SKUs that are *not* in a given bucket. On a `set` (or a `dict` key lookup), `__contains__` computes `hash(x)` once, jumps to a location derived from that hash, and compares against whatever is stored there. That is O(1) on average, independent of how many elements the set holds. The internal machinery that keeps it O(1) - buckets, probing, load factor, resizing - is hash-table territory and not what this question is about; what matters here is the observable contract: a constant-time average lookup, with a rare linear worst case that real workloads do not hit. ## The arithmetic that makes it a bottleneck A pick-list builder that walks m order lines and tests each against a stock list of n rows does O(n*m) equality comparisons. With 20,000 order lines against 50,000 stock rows that is up to a billion `__eq__` calls, each of them an interpreted-level operation. Converting the stock rows to a set costs one O(n) pass and a hash per element, after which the loop is O(m) lookups: O(n+m) in total. The crossover is immediate - two or three lookups already beat the scan on a list of any real size - which is why 'is this repeated membership testing over a collection that does not change?' is the single most reliable place a set earns its keep. ## The mistake that erases the win ```python picks = [s for s in lines if s in set(stock)] # rebuilds the set every iteration ``` This is still O(n*m), and now with hashing overhead on top: the `set(stock)` call sits inside the comprehension's loop body, so it runs once per line. Hoist it: ```python in_stock = frozenset(stock) picks = [s for s in lines if s in in_stock] ``` The same error hides inside functions - a helper that takes the list and does `if sku in set(rows)` is quadratic no matter how it is called. When you profile and the fix does not help, this is usually why. ## What the set costs you A senior answer does not stop at 'use a set'. Four costs, all of them real: **Memory.** A set stores hashes and slot bookkeeping on top of references to the same objects, and keeps deliberate empty space so lookups stay fast. On a service already holding a 2.4 GB working set, materialising a set beside every large list is how you turn a CPU problem into an out-of-memory one. Build the set for the collection you probe repeatedly, not for every list in sight, and drop it when the pass is over. **Lost multiplicity and order.** A set answers 'is it there', never 'how many' or 'in what order'. If the pick list has to honour quantities, `collections.Counter` is the structure that keeps the counts while retaining O(1) lookup; if it must preserve sequence, keep the list for output and use the set only as the membership oracle. **Hashability.** Elements must be hashable, so a list of dicts or of mutable records cannot go into a set as-is - you index on a derived key instead. **Staleness.** This is the failure that survives review. The set is a snapshot taken at build time. If the stock list is refreshed mid-run, or the set is cached on a module or an object and outlives the data it was derived from, every lookup afterwards answers from a stale cached value: SKUs that went out of stock still pick, newly received SKUs are reported missing, and nothing raises. Two defences worth naming - derive the set at the same moment you read the data and let it die with the pass, or use a `frozenset` so that at least nothing can quietly mutate the oracle behind you. If the data really does change during the run, the set must be invalidated with it, and an explicit rebuild is easier to reason about than a cache-invalidation rule. ## When a set is not the answer If you test membership once, the O(n) build costs more than the O(n) scan - just scan. If elements are unhashable and no derived key exists, a set is off the table. If memory is the binding constraint and the collection is already sorted, `bisect.bisect_left` on the sorted list gives O(log n) lookups with no extra structure at all. And if the question is really 'do these two collections share anything', `set(a).isdisjoint(b)` short-circuits on the first common element rather than materialising an intersection. ## How to demonstrate it rather than assert it The credible version of this answer is measured. `timeit` on both spellings with realistic sizes shows the gap in one line, and a profile of the real job shows whether membership is actually the hot path - sometimes it is not, and the real cost is parsing or I/O, in which case swapping the structure changes nothing and you have spent your credibility on the wrong fix.

  • The pick list must also honour quantities. What changes when a set no longer suffices?
    A set answers presence only, so quantities need a mapping: `collections.Counter` over the stock rows keeps per-SKU counts while preserving O(1) average lookup, and `in` still works on it. Decrementing as you allocate gives you both the membership test and the running balance in one structure. If the counts come from elsewhere, a plain dict from SKU to quantity is the same tradeoff without Counter's arithmetic helpers.
  • A cached set of in-stock SKUs is held on a long-lived object. What goes wrong, and how do you defend against it?
    It is a snapshot: once the underlying stock data changes, every lookup answers from a stale cached value, so withdrawn SKUs keep picking and new ones read as missing - silently, with no exception anywhere. Defend by giving the derived set the same lifetime as the data it came from, rebuilding it explicitly at each refresh rather than mutating it in parallel, and storing it as a frozenset so no other code path can drift it out of agreement with the source.
  • When would you keep the list and not build a set at all?
    When you test membership once or twice - the O(n) build costs as much as the O(n) scan. When elements are unhashable and there is no sensible derived key. When memory is the binding constraint and the data is already sorted, in which case `bisect.bisect_left` gives O(log n) lookups with no extra structure. And when profiling shows membership is not the hot path, which is more often true than people expect.

Scanning a list is reading a warehouse inventory sheet line by line for every SKU you are asked about; a set is a labelled bin wall where you walk straight to the label - but only until someone restocks and nobody repaints the labels.

saying these in an interview costs you the question

  • Calls set membership constant time with no mention of the build cost
  • Leaves the set(...) conversion inside the loop
  • Ignores the extra memory a parallel set costs
  • Swaps a list for a set where duplicate counts mattered
  • Caches a derived set with no plan for refreshing it
  • Asserts the speedup without measuring the actual hot path

context

resolving links…