Your ingest budget forbids touching every packet, yet exact detection is Omega(n) — which guarantee do you weaken?
answer
- the bound is not the negotiable part
- which promise can the business lose?
- exactness, window size, or where work is paid
- one-sided error has a direction you choose
- moving work is not removing work
basics
~20 sA proven lower bound is not the negotiable part, so the only lever is the problem statement: weaken exactness, shrink the input covered, or move the cost off the latency path. Pick the relaxation whose failure mode the business can absorb.
solid answer
~50 sMake it explicit first that the floor is not an engineering target — no tuning gets under Ω(n) for an exact answer over the full stream. That reframes the meeting from "optimise harder" to "what may we stop promising?" Four levers exist. Sample, and report a rate rather than a verdict. Approximate with a filter whose error is one-sided, so you choose which way mistakes go. Shrink n by bounding the detection window, which leaves the bound intact but applies it to less data. Or relocate the work to ingest, where the total is unchanged but the query path is fast. The choice is not technical: it turns on whether a missed duplicate or a false alarm costs more, and who maintains a probabilistic structure a year from now. Choose deliberately, state the error rate as a number, and set a revisit trigger.
go deeper
Understand that a proven lower bound cannot be engineered away, so the useful discussion moves to what the system is allowed to answer rather than how fast it can answer the original question.
Explain the relaxations available — sample, approximate, shrink the input, or move the work off the latency path — and be precise about what each one costs in correctness.
Show you pick an error direction on purpose: which of a missed duplicate or a false alarm your system absorbs, and how you would measure the real rate in production rather than the theoretical one.
Own the tradeoff and its blast radius. Name who lives with the error budget, who maintains the approximate structure a year from now, and what the error rate does when traffic grows tenfold.
## Why this is a leadership call and not a tuning task Most performance problems are engineering problems: a profile, a hot loop, a bad constant. This one is not. When a proven lower bound sits between the requirement and the budget, no amount of engineering closes the gap, because the bound quantifies over every algorithm anyone could write. The only remaining variable is the requirement itself. Recognising that early is what stops a team from spending three sprints on something that provably cannot exist. The reframe to say out loud: *we are not choosing an algorithm, we are choosing which promise to stop making.* ## The four levers **Sample.** Inspect a fixed fraction of the stream and report a duplicate *rate* rather than a verdict on any specific packet. This is right when the consumer is a dashboard, an anomaly signal, or a capacity model — anything that wants a trend. It is wrong when a single duplicate has consequences, because sampling guarantees you will miss some. **Approximate with one-sided error.** A probabilistic membership filter answers in constant time and small constant space, and — critically — errs in exactly one direction. A Bloom-style filter never reports "not seen" for something it has seen; it sometimes reports "possibly seen" for something new. That asymmetry is the whole design lever. If a false alarm is cheap and a miss is expensive, you want that direction; you then confirm every "possibly seen" against an exact store, so the filter acts as a cheap gate over an expensive check. If the costs run the other way, this structure is the wrong shape and you need a different relaxation. **Shrink what n counts.** Bound the detection window to the last few seconds, or restrict detection to a subset of the key space that matters. The Ω(n) bound is untouched — it simply now applies to a much smaller input. This is the most underrated lever because it keeps exactness intact, and the loss (duplicates separated by more than the window are invisible) is often perfectly acceptable and easy to explain. **Relocate the work.** Pay per packet at ingest so queries are cheap. Total work stays Ω(n); it moves off the path that has the budget. This is not a relaxation of correctness at all, and it should always be the first thing checked, because it costs nothing but engineering. ## Choosing between them The technical comparison is the easy half. The questions that actually decide it: - **Which error direction can you absorb?** For a billing or exactly-once path, a missed duplicate is a double charge and a false alarm is a retry — the asymmetry is enormous and it points at one specific structure. For a spam or abuse signal, the asymmetry usually runs the other way. Deciding this by default rather than deliberately is the most common failure. - **Whose budget owns the error?** An error rate that is invisible to engineering is often extremely visible to support, finance or a downstream team. If nobody outside the team has agreed to the number, you have not made a decision, you have made an assumption. - **Who operates this in a year?** A probabilistic structure has tuning parameters whose meaning is not obvious from the code, and its error rate drifts as traffic grows. An exact scan over a bounded window has no parameters and fails loudly. Choosing the more sophisticated option obliges someone to understand it at 3 a.m. - **What happens at ten times the traffic?** Sampling ratios and filter sizing that were correct at launch quietly degrade — a filter sized for one load gets denser and its false-positive rate climbs. A relaxation without a scaling story is a relaxation with an expiry date nobody wrote down. ## Making the decision durable Write three things next to the code: the input rate the sizing assumed, the error budget as a number with a named owner, and the trigger that forces a revisit (a traffic multiple, an observed error rate, a change in what the consumer does with the answer). Then instrument the actual error rate, not the theoretical one, because the theoretical one assumes a key distribution that production will eventually violate. ## The claim to reject The answer this question hunts for is "we will profile and optimise until it fits." Against a proven floor for the stated problem, that plan cannot succeed, and the seniority signal is being able to say so, explain why the floor is a proof rather than a benchmark result, and immediately offer the menu of relaxations instead. The second-worst answer is picking the clever approximate structure without ever naming which direction its errors point or who agreed to them.
- Which error direction would you choose for a duplicate detector guarding a billing pipeline?The one that never misses. A missed duplicate means charging a customer twice — expensive, visible and reputationally costly — while a false alarm just triggers a confirmation lookup. So use a filter with no false negatives as a cheap gate, and verify every 'possibly seen' against an exact store. The gate absorbs the volume; the exact check absorbs the correctness requirement.
- How do you keep a decision like this from quietly rotting after launch?Record the assumed traffic rate, the error budget as a number, and its owner alongside the code. Instrument the observed error rate rather than trusting the theoretical one, alarm when it drifts, and set an explicit revisit trigger such as a traffic multiple. Sizing that was correct at launch degrades silently as load grows, and without a trigger nobody notices until the error becomes an incident.
You cannot argue a bridge's weight limit down. You change the load, the route, or the schedule.
saying these in an interview costs you the question
- Proposes optimising until the proven bound is beaten
- Adopts an approximate structure without naming an error budget
- Assumes false positives and false negatives cost the same
- Treats moving work to ingest as removing the work
- Ignores who will operate and retune the structure later