A sublinear exact duplicate detector over an n-packet stream is proposed — how do you evaluate it?
answer
- ask what the algorithm never looks at
- let an adversary fill in the input
- plant the duplicate in the unread packet
- two inputs, identical run, different answers
- work may have moved to ingest
basics
~20 sAn algorithm that skips even one packet is defeated by an adversary who plants the duplicate there, so exact detection over a raw n-packet stream is Omega(n). A sublinear claim means work moved, the guarantee weakened, or n means something smaller.
solid answer
~50 sRun the adversary argument in the room. If the detector reads fewer than n packets, name one it never reads; set that packet equal to another and the correct answer flips, while the algorithm's execution is byte-for-byte identical — so it is wrong on one of the two inputs. That makes exact duplicate detection over a raw stream Ω(n), and no data structure repeals it. Then ask what the claim actually meant, because it is usually one of three real things: the work moved to ingest, so every packet is still touched once but the *query* is cheap; the guarantee weakened to probabilistic membership with one-sided error; or n is the query count rather than the data. Each is a legitimate engineering move and none of them is a faster algorithm for the stated problem. Ask which one is on the table, and get it written into the design.
go deeper
Know that an exact answer over unsorted data has to look at every item, so the word 'sublinear' should immediately prompt the question of what the algorithm is allowed to skip.
Be able to run the adversary argument: name an item the algorithm never reads, change it, and show that the correct answer moves while the execution does not.
In review, separate the three real explanations — cost moved to ingest, guarantee weakened, or n measured over something smaller — and get the design to say which one it means.
Own the standard of evidence your organisation accepts for performance claims. A benchmark reports constants on one distribution; a proof reports a floor. Decide which is required before a claim becomes a commitment.
## Why this claim comes up "We can detect duplicates without scanning everything" is one of the most common performance claims in a design review, and it is usually made in good faith. It is also, as stated, impossible — and knowing how to show that in thirty seconds without deflating the person who said it is a senior skill. ## The input-reading floor Some problems have a floor simply because their answer depends on every part of the input. Exact duplicate detection over an unordered stream is one: the correct output for "does this batch of n packets contain two identical payloads?" can be flipped by editing a single packet. The argument, stated as an adversary game: 1. Suppose an algorithm A always halts after reading fewer than n packets and always answers correctly. 2. Run A on an input where all n packets are distinct. It reads some subset and reports "no duplicate". There is at least one packet p it never read. 3. Construct a second input identical to the first except p is changed to equal some other packet. 4. A reads exactly the same packets and sees exactly the same bytes, so it executes identically and reports "no duplicate" again. 5. But the second input *does* contain a duplicate. A is wrong on it. So no such A exists, and exact detection is Ω(n). Note what makes the argument work: the adversary fills in the input *after* seeing what the algorithm examined. That is the general shape of every input-reading lower bound, and it is worth being able to reproduce it on the spot for whatever the problem is. ## Problem bound versus algorithm bound This is the distinction the whole conversation turns on. A bound on an **algorithm** describes one program: "this scan costs O(n)". A bound on a **problem** quantifies over every algorithm that could ever be written: "nothing correct costs less than Ω(n)". The first can be improved by better engineering. The second cannot be improved at all — it can only be sidestepped by changing the problem. So when the numbers do not add up, the productive question is never "can we optimise harder?" It is "which part of the problem statement is not actually required?" ## The three things a sublinear claim usually means **The work moved to ingest.** A membership structure built as packets arrive answers later queries in expected constant time. Every packet was still touched exactly once; the total remains Ω(n). What improved is the *per-query* cost, which is often exactly what the system needed. This is a real win and it does not contradict the bound — but it must be stated as "amortised across ingest", not as "sublinear". **The guarantee weakened.** A probabilistic membership filter answers in constant time and constant space per query, with one-sided error: it may report "possibly seen" for something never seen, but never reports "not seen" for something seen. That is a different problem — approximate membership rather than exact detection — and the bound for exact detection says nothing about it. **n was measured over something else.** "Sublinear in the number of queries", "sublinear in the retention window", or "we only inspect flows, not packets". Every one of these is a legitimate design, and every one of them silently redefined the input. Always ask: n of *what*? ## What does not work **Parallelism.** Splitting the stream across sixteen workers cuts wall-clock time by up to sixteen, and total work stays Ω(n) — because sixteen workers still collectively read every packet. Lower bounds count work, not elapsed time, and confusing the two is the single most common error in these conversations. **A better hash function.** It changes constants and collision behaviour; it does not let you skip packets you never hashed. **A benchmark.** A benchmark measures constants on one input distribution. Lower bounds are worst-case statements over all inputs. A detector that is fast on production traffic today tells you nothing about whether the bound holds, and everything about whether today's traffic resembles the benchmark. Both are useful; they answer different questions. ## How to run the review Ask three questions, in order: what is n measured over; is the structure built during ingest or assumed to exist; and is the answer required to be exact on every input. Nine times out of ten, one of those three answers reveals the claim to be a legitimate design with an imprecise description, and the fix is a sentence in the doc rather than a redesign.
- The teammate's benchmark really is faster than a full scan on their capture file. What does that prove?That their constants and input distribution are favourable, not that the bound is wrong. Check first whether the harness preloads or pre-indexes the capture outside the timed region — that is the usual explanation. A benchmark is evidence about one distribution; a lower bound is a proof about all of them. Both belong in the review, answering different questions.
- Where would you attack the assumptions of the Omega(n) argument if you wanted sublinear to be possible?The proof assumes raw unordered input, exact correctness on every input, and that the algorithm starts from nothing. Break any one and sublinear becomes reachable: accept a probabilistic answer, require the source to deliver packets pre-sorted or pre-hashed, or maintain an index at write time so the query is not starting cold. Each moves cost or weakens a promise — which is exactly the tradeoff to make explicit.
An auditor who skips a warehouse box cannot certify the warehouse contraband-free, because that is exactly the box someone hides it in.
saying these in an interview costs you the question
- Believes a clever index makes an uningested scan sublinear
- Counts query time only and ignores ingest cost
- Calls a probabilistic filter an exact detector
- Thinks parallelism reduces total work, not just latency
- Accepts a benchmark as proof no faster algorithm exists