skip to content

With 20 overlapping taint filters the avoid-all sum needs 2^20 terms - how do you decide what to compute instead?

level: principalimportance: should knowfreq 30%

answer

  1. each term is a measurement, not an operation
  2. ask what you can actually scan
  3. one pass costs n times k
  4. disjoint segments remove the overlap entirely
  5. truncate for bounds, sample for intervals

basics

~20 s

Decide by what you can touch. With the raw records in reach, one pass evaluating a compound predicate costs about n times k and is exact; the signed sum is for when only aggregate set sizes are available, and at twenty filters its million terms mean a million measurements.

solid answer

~50 s

The signed sum needs one measured intersection size per subset of the filters - `2^20` is over a million of them - and each is a real aggregate over the data, not a line of arithmetic. So the first question is not how to compute the sum faster but whether you need it at all. If the records are scannable, a single pass that tests `matches no filter` per record is exact, linear in `n x k`, and trivially explainable. The signed sum earns its place only when the records are out of reach and you have set sizes alone. If you are stuck with aggregates, the options are: restructure the conditions into mutually exclusive segments so the overlaps vanish; exploit symmetry or structure to collapse subsets into groups; truncate deliberately and report a bounded interval; or sample and report a confidence interval. Each trades exactness for a cost you can state.

code

pseudocode · 10 lines
pseudocode
clean = 0
for each record r in feed:
    tainted = false
    for each filter f in filters:          // k filters
        if f(r) then
            tainted = true
            break                          // short-circuit on first match
    if not tainted then
        clean = clean + 1
return clean                               // exact, cost about n x k

go deeper

for a junior

Recall that the exact clean count needs one term per combination of conditions, so the work doubles with every condition added.

for a middle

Explain why a single pass over the records with a compound predicate is exact and costs about n times k, and when aggregate-only access removes that option.

for a senior

Show the operational alternatives and their guarantees: truncation gives a bounded interval with a known direction, sampling gives a confidence interval, and estimated terms can drive the result negative.

for a principal

Own the modelling decision: whether to restructure the conditions into mutually exclusive categories, who owns the precedence rules that forces, and what the organisation loses when a doubly-tainted record reports under one heading.

## The decision, not the formula Twenty taint filters over a deduplication feed and a compliance question - how many records tripped none of them - is not a mathematics problem in the first instance. The signed sum over all subsets has `2^20 = 1,048,576` terms. The arithmetic is nothing; a million additions are microseconds. What is not nothing is that **each term is a measurement**: the number of records caught by that particular combination of filters. A million aggregate queries over a data feed is a pipeline that will not finish, and this is where engineers lose the thread by optimising the sum instead of questioning it. ## First question: what do you actually have access to? | what you hold | the right instrument | cost | |---|---|---| | the raw records | one pass evaluating a compound predicate | about `n x k`, exact | | per-filter and per-combination totals only | the signed sum | up to `2^k` measurements, exact | | totals for a few combinations | a truncated sum | cheap, gives a bounded interval | | a sample of records | scan the sample | cheap, gives a confidence interval | The principle exists for the second row. It was built to answer questions about set sizes when the elements themselves are unavailable - an aggregate warehouse, a pre-computed report, a counting sketch. When you can iterate the records, evaluating the conditions directly per record short-circuits the whole problem: the first filter that matches ends the record's evaluation, and the loop is linear in the number of filters rather than exponential. ## Second question: can the conditions be restructured? Overlap is what makes the sum large. If the conditions can be redefined as **mutually exclusive segments** - each record carries exactly one taint category, chosen by a documented precedence - then the clean count is a single subtraction, the report is explainable to an auditor, and the `2^k` problem never arises. This is usually a data-modelling decision rather than a mathematical one, and it is the change with the longest payoff: every future question about the segments also becomes a one-line answer. The cost is real - precedence rules are arbitrary decisions someone must own, and a record with two genuine problems now shows under one heading. Where the conditions are symmetric, structure does the collapsing for you: if every subset of a given size has the same intersection size, all `C(k,j)` of them share one term and the sum shrinks to `k+1` terms. That is a property of the problem, not a technique you can apply to arbitrary filters. ## Third question: is exactness required? Two cheaper instruments both come with a statement of what they guarantee: 1. **Truncate deliberately.** Partial sums alternate around the answer, so stopping after the single-filter terms gives an upper bound on the union and hence a lower bound on the clean count; going one group further flips both. Report the interval and the truncation depth, never the midpoint as if it were the count. 2. **Sample and scan.** Draw records, evaluate all `k` filters on each, and report the proportion with an interval. Often the honest answer when the exact figure is not what the decision needs. There is one more failure mode worth naming: if the intersection sizes are themselves **estimates** rather than exact counts, the signed sum is numerically hostile. It adds and subtracts large, similar quantities to land on a small one, so independent errors in the big terms accumulate while the true answer stays small. A sum whose terms are approximations can produce a clean count that is negative - a result that is arithmetically possible and physically impossible, and a reliable signal that the inputs were estimates. ## What a strong answer sounds like It does not begin with the formula. It begins by asking whether the raw records are reachable, and only reaches for the signed sum when they are not. It names the restructuring option as the durable fix, states the cost of the precedence rules that restructuring forces, and offers the bounded or sampled answer as an explicit trade with a stated guarantee. It also says plainly that `2^k` is a count of **measurements**, not of arithmetic operations - the mistake that makes a million-term sum sound tolerable. ## The line to hold The principle is exact and assumption-free, which makes it tempting to treat as the default. It is the right instrument for a narrow situation: few conditions, or aggregate-only access, or exact counts required by an external obligation. Outside that situation, the engineering answer is to change what you are computing - not to compute a hopeless sum more cleverly.

  • If the intersection sizes are estimates rather than exact counts, what goes wrong with the signed sum?
    It becomes numerically hostile. The sum adds and subtracts large, similar quantities to reach a small one, so independent errors in the big terms accumulate while the true answer stays small. A clean count that comes out negative is arithmetically possible here and is a reliable signal that the inputs were approximations.
  • What is the cost of restructuring twenty overlapping filters into disjoint taint categories?
    Someone must own a precedence order, which is an arbitrary decision, and a record with two genuine problems then appears under only one heading. In exchange every count becomes a single subtraction, the report is explainable to an auditor, and adding a category no longer doubles anything.
  • When is the signed sum still the right instrument at twenty conditions?
    When the conditions are symmetric enough that subsets of the same size share a term value - then `2^k` subsets collapse to `k+1` groups - or when only a handful of the intersections are non-empty, so most terms are zero and can be skipped. Both are properties of the problem, not techniques you can impose.

saying these in an interview costs you the question

  • Treating 2^k as arithmetic cost rather than measurement cost
  • Optimising the signed sum when the raw records are scannable
  • Reporting a truncated sum as the exact count
  • Summing estimated intersection sizes and trusting the result
  • Claiming the principle needs the conditions to be independent