Rabin-Karp or a linear-guarantee matcher per pattern: how do you screen submissions against 50,000 known snippets?
answer
- where does the pattern count enter the cost
- one pass or k passes over the text
- the fingerprint is computed once, tested many times
- spurious hits scale with needles over range
- compare against a multi-pattern automaton fairly
basics
~20 sOne rolling-hash pass fingerprints every window once and tests it against a set holding all 50,000 snippet fingerprints, so needle count barely touches scan time. A single-pattern matcher per snippet costs 50,000 passes per submission — no latency budget survives that.
solid answer
~50 sRabin-Karp is the rare case where the fingerprint-plus-verify design beats algorithms with better single-pattern guarantees, because the fingerprint is computed **once per offset** and then looked up against however many needles you hold. Cost is O(n) to roll plus O(k*m) to build the needle set, versus O(k*(n+m)) for k independent scans. The constraints to voice: all snippets in one pass must share a window length, so you group by length and pay one pass per distinct length; spurious confirmations scale like n*k/M, so the fingerprint range must be widened as the needle set grows; and each confirmation may need the real snippet fetched to compare against. The honest alternative is a multi-pattern automaton such as Aho-Corasick, which gives a worst-case guarantee — at the price of a built structure in memory, a rebuild when the corpus changes, and more machinery for the team to own.
go deeper
Recall the core asymmetry: a fingerprint computed once per position can be tested against many needles at once, whereas a single-pattern matcher must be run once per needle.
Work the arithmetic aloud — one O(n) pass plus an O(k*m) build against k passes of O(n+m) — and name the fixed-window-length constraint that a multi-needle pass imposes.
Show the operational consequences: spurious confirmations growing with the needle count, the cost of fetching snippet text to confirm, and the metric that warns you before latency does.
Own the decision and its reversal. Weigh memory ceilings, corpus update rate, who supplies the text, and team maintenance cost, then write down the explicit metric threshold that triggers moving to a guaranteed multi-pattern matcher.
## Why the pattern count changes the answer For a single needle, an algorithm with a worst-case linear guarantee is strictly the better engineering choice: same asymptotics as the expected case, no probabilistic tail, no verification cost. The picture inverts at scale, because that guarantee is *per pattern*. Screening one submission against k = 50,000 snippets means k scans: O(k*(n+m)). At n = 100,000 symbols that is five billion symbol steps per submission before anything useful happens. The rolling-hash screen changes the multiplication. Fingerprint each of the n windows once, in constant time each, and test that one value against a set containing all k snippet fingerprints. The scan is O(n) regardless of k. The needle set costs O(k*m) to build, once, offline, and is reused across every submission. The pattern count moves out of the per-request path and into a build step — which is the whole architectural argument. ## The constraints you must state, because they are the real design work **Fixed window length.** A rolling hash of width m only produces width-m fingerprints. Snippets of different lengths cannot share a pass. In practice you normalise the corpus to a fixed shingle width — 40 symbols, say — or you group snippets by length and run one pass per distinct length, which brings back a multiplier equal to the number of distinct lengths, not the number of snippets. Choosing one canonical width is a product decision (how short a reused passage still counts) disguised as an engineering one. **Spurious confirmations scale with k.** With a uniform-looking fingerprint into M values, each window has roughly k/M chance of hitting *some* needle by accident, so over n windows the expected spurious confirmations are about n*k/M. This is the number that decides whether the design holds. At n = 10^5, k = 5*10^4 and a narrow 32-bit-scale range, n*k/M exceeds one — you are confirming constantly and the screen has collapsed into something quadratic. Widen the range to a 64-bit-scale modulus and the same numbers give a value near 10^-9: effectively never. **The needle count sits in the numerator, so the range must grow as the corpus grows** — a fingerprint width that was ample at 5,000 snippets is not automatically ample at 500,000. **Confirmation is not always cheap.** A hit tells you *which* needle fingerprint matched; confirming requires the needle's actual text. If the corpus lives out of process, each confirmation is a fetch, and a fetch is orders of magnitude more expensive than the O(m) comparison. That turns the spurious rate from a CPU concern into a tail-latency and dependency-load concern, and it is the argument for keeping the hot snippet text local or accepting a two-stage confirm. ## The alternative, argued fairly A multi-pattern automaton — Aho-Corasick is the standard one — matches all k needles in a single pass with a worst-case guarantee, handles mixed lengths natively, and never produces a false candidate. If the guarantee matters, that is the right answer and you should say so rather than defending the hash out of loyalty. What it costs: a structure whose size grows with the total needle length, held in memory on every screening host; a rebuild step when the corpus changes, which for a corpus updated continuously is its own pipeline; and materially more code for the team to understand, test and debug at 3 a.m. The rolling-hash screen's index is a set of numbers — trivially sharded, trivially updated incrementally, trivially explained to a new engineer. ## How a lead should actually decide Start with the numbers, not the preference. Write down n, k, the update rate of the corpus, the latency budget per submission, the memory ceiling per host, and who supplies the text. If the text is user-supplied and adversarial collisions are plausible, the hash screen needs randomized parameters and a bail-out or it is a denial-of-service surface. If the corpus mutates hourly, the automaton's rebuild is a recurring cost the hash screen does not have. If the memory ceiling is tight and the needle set is large, the set of fingerprints wins outright. Then make the decision reversible. The hash screen is a few hundred lines and produces a confirmed-match interface identical to the automaton's. Ship it, instrument confirmations per submission and p99 latency, and let those metrics — not an asymptotic argument — trigger the migration at 10x. State the trigger explicitly in the design document: "if confirmations per submission exceed X or the corpus passes Y needles, we move to the automaton." A tradeoff with a written trigger is a decision; one without is a preference.
- What has to be true of the snippet corpus for a single rolling-hash pass to work?Every snippet screened in that pass must have the same length, because a width-m roll only produces width-m fingerprints. Mixed lengths mean grouping by length and one pass per distinct length — acceptable when there are a handful of widths, ruinous when there are hundreds. Most designs normalise to one canonical shingle width and accept that reuse shorter than that width is out of scope.
- At 10x the corpus size, what breaks first in the hash screen?The spurious confirmation rate, which grows linearly with the needle count: roughly n*k/M. Memory for the fingerprint set also grows linearly but stays cheap, and scan time barely moves. So the first symptom is confirmations per submission climbing, taking p99 latency with them — especially if each confirmation fetches snippet text. The lever is widening the fingerprint range before the corpus grows, not after.
- When would you take the automaton despite its build and memory cost?When the guarantee is worth paying for: adversarial or untrusted input where a probabilistic bound is a denial-of-service surface, a hard per-request latency SLO with no tolerance for a confirmation storm, or a corpus of mixed lengths that would otherwise need many passes. If the corpus is also stable enough that rebuilds are rare, most of the automaton's cost disappears and its downside is mainly the code the team must own.
saying these in an interview costs you the question
- Assumes one rolling-hash pass handles mixed snippet lengths
- Ignores that spurious confirmations scale with the needle count
- Picks the better single-pattern bound without multiplying by k
- Treats verification as free when snippet text is remote
- Chooses on asymptotics without stating the latency and memory budgets