Is a suffix array worth its memory for thousands of substring queries over a fixed 10^8-character archive?
answer
- Who pays, once or every time?
- Multiply the per-query cost by k
- The build is worth a few dozen scans
- Four bytes per character, resident somewhere
- A growing archive invalidates every rank
basics
~20 sUsually yes: past a few dozen queries the one-time build amortises, while a per-query scan never stops costing. Decide on resident memory — roughly four bytes per character plus the archive — how often the archive changes, and who will own the index.
solid answer
~50 sDo the arithmetic before the architecture. Scanning is O(n) per query, so `k` queries cost O(kn) forever; a suffix array costs O(n) to O(n log n) once and then O(m log n) per query — for a short fragment that is a few hundred character reads instead of 10^8. Construction is worth a constant number of scans, so the crossover sits in the dozens of queries, and thousands is comfortably past it. What can still kill the idea is not asymptotics: 10^8 offsets is around 400 MB resident on top of the archive itself, construction takes real minutes, and the structure is static — an archive that keeps growing invalidates ranks, forcing a rebuild or an index per sealed chunk. I would refuse the index for one-off searches, for a constantly changing corpus, or when the queries are really whole-word prefix lookups, where a prefix tree over the vocabulary is much smaller.
go deeper
Recall the shape of the tradeoff: scanning costs the same every single query, while an index costs a lot once and then very little each time. Knowing which cost repeats is most of the answer at this level.
Work the arithmetic out loud — per-query scan cost times the query count against build cost plus cheap queries — and state the per-query bound for a suffix array with the pattern length in it.
Convert the bounds into operational numbers: megabytes resident, minutes to build, latency before and after, and what a growing archive does to a structure whose ranks are fixed at build time.
Own the call and its exit: name the query volume that justifies the memory, the rebuild cadence the freshness requirement implies, the chunked design that bounds staleness, and the workloads where you would refuse the index outright.
## Frame the decision as who pays, and how often Two cost curves meet here. A linear scan over the archive charges the full text length to **every** query and charges nothing up front. A suffix array charges a large one-time build and then charges each query almost nothing. The question is never "which algorithm is better" — it is where the two lines cross for the workload actually in front of you, and whether the winning line fits the machine. **The arithmetic.** Let `n` be the archive length, `k` the number of queries, `m` the fragment length. | Strategy | Up-front | Per query | Total | |---|---|---|---| | Scan per query | none | O(n) | O(k·n) | | Suffix array | O(n) to O(n log n) | O(m log n), or O(m + log n) with an LCP array | O(n log n + k·m log n) | With `n = 10^8`, `log n` is about 27. To a first approximation the build costs the same as a couple of dozen scans — and honestly more than that, because construction constants are much larger than a sequential memory scan's. Each query then drops from 10^8 character reads to a few hundred. Thousands of queries is one to two orders of magnitude past the crossover: the index wins, and not narrowly. ## Then check the constraints that asymptotics do not see **Resident memory.** Roughly four bytes per position with 32-bit offsets — about 400 MB for this archive — plus the archive itself, which the index cannot answer without. If you add an LCP array, budget for it too. On a shared fleet host that number, not the query bound, decides whether the index exists. **Build time and its window.** Construction is minutes, single-shot, memory-hungry at its peak. That has to fit somewhere: a nightly job, a sealed-segment pipeline, a warm-up before the host serves traffic. "We will build it on first query" is how you get a multi-minute p100 on someone's dashboard. **Freshness.** A plain suffix array is static. Appending text shifts offsets and reorders ranks; there is no cheap patch. If the archive is genuinely fixed, this is free. If it grows, the honest designs are: rebuild on a cadence and accept staleness, or seal the archive into chunks, index each sealed chunk, and scan only the unsealed tail. That second design is usually the right one and it is worth proposing unprompted, because it converts a hard freshness problem into a bounded one. **Ownership.** A hand-rolled index is code someone must debug at 3 a.m. two years from now. Argue for the simplest structure that clears the requirement, prefer a construction whose output is checkable (a suffix array's sortedness is verifiable in linear time), and be explicit that this cost is real rather than a reason to be timid. ## Where I would refuse to build it - **One pattern, one text, once.** A single linear-time pass over the text is the whole answer; an index that takes minutes to serve one query that takes seconds is negative value. - **A corpus that changes faster than it can be indexed.** If rebuild cadence cannot keep up with write rate, the index is always answering yesterday's question. - **Queries that are not really substring queries.** If analysts search for whole tokens or their prefixes rather than arbitrary mid-word fragments, a structure over the vocabulary — a prefix tree, or a term index over extracted tokens — is dramatically smaller than an index over every character position, because the number of distinct tokens is far below the number of positions. - **Query volume nobody measured.** "Thousands" should come from a log, not from a hope. The entire decision hinges on `k`, so measuring it is the first task, not the last. ## What a strong answer sounds like It states the crossover with numbers, it converts the asymptotic memory claim into megabytes, it raises staleness before being asked, it names the cheaper alternative for the workloads that do not need a full substring index, and it commits: for thousands of ad-hoc fragment queries against a genuinely fixed archive, build the index, keep the offsets and the text on the same host, and add the LCP array only if the measured query mix has long fragments. ## The wrong answers to steer around The first is direction-blind: "O(n log n) is worse than O(n), so scanning wins." It compares a one-time cost against a per-query cost as if they were the same currency. The second treats the index as free and never mentions that hundreds of megabytes must live somewhere. The third quietly assumes new records can be appended into an existing suffix array. The fourth is building the index at all for a workload nobody has counted.
- Roughly how many queries before the build pays for itself?Dozens, not thousands. Scanning charges the full archive length per query; the index charges a constant multiple of one scan up front and then almost nothing per query. Since construction is worth on the order of the log factor in scans — and somewhat more once constants are honest — a few dozen queries clears it. That is why measuring the real query count is the first step.
- The archive gains several megabytes an hour. Now what?A plain suffix array cannot absorb that: appended text shifts offsets and reorders ranks. Seal the archive into chunks, build one index per sealed chunk, and answer a query as a fan-out over chunk indexes plus a direct scan of the small unsealed tail. Rebuild cadence then becomes a tunable knob rather than a correctness problem, and stale results are bounded by chunk size.
- Which workloads would send you away from a suffix structure entirely?A single pattern searched once against a single text — a linear-time single-pattern match beats any index that must first be built. Whole-word or word-prefix lookups over a bounded vocabulary — a prefix tree over the distinct tokens is far smaller than an index over every character position. And exact-field equality, which is a hash lookup, not a substring problem.
- How would you justify the memory to someone who owns the host budget?In their currency: state the index size in megabytes, the per-query latency before and after, and the query volume from the logs. Then offer the fallback explicitly — scan-per-query stays correct and costs zero memory, at a per-query latency of seconds. Framing it as a purchased latency reduction with a known price makes it a decision rather than a preference.
Building the index is paving a road: absurd for one trip, obviously right by the thousandth — and if the terrain shifts every week, the repaving bill is the whole argument.
saying these in an interview costs you the question
- Says an O(n log n) build loses to an O(n) scan, so never build
- Treats the index as free and never estimates its resident size
- Assumes new records can be appended into an existing suffix array
- Builds a full index for a single one-off fragment search
- Quotes asymptotics without ever estimating the query volume