When does an interval DP table beat O(1)-space center expansion for palindromes in long gene reads?
answer
- same time, different memory
- what does the table produce that expansion cannot?
- answers for every interval, reusable
- who reads those answers more than once?
- count the cells at the real read length
basics
~20 sOnly when something else will query the table. Both methods cost O(n^2) time for one longest symmetric run, but the table also costs O(n^2) memory. It pays off when an enclosing computation asks "is i..j symmetric?" many times, or when you need counts over all intervals.
solid answer
~50 sFor a single answer — the longest symmetric stretch in one read — centre expansion wins outright: same O(n^2) worst-case time, O(1) auxiliary space, no allocation per record, and it parallelises trivially across centres. The interval table costs n^2 cells, which at 5,000 bases is 25 million entries per read and is simply unaffordable per worker in a batch job over millions of records. The table earns its memory when its cells are **read repeatedly**: an enclosing computation that splits a read into the fewest symmetric segments consults palindromicity for a great many pairs and would otherwise recompute them; likewise counting all symmetric intervals, or precomputing once and answering many range queries. Also note the deletion variant has no constant-space form at all. And be honest about scale: at hundreds of thousands of bases neither is viable, because O(n^2) time is the binding constraint before memory is.
go deeper
Be ready to say that expanding around centres needs almost no extra memory while the table needs a cell for every pair of endpoints, and that both take about the same time.
Explain what the table actually produces — constant-time symmetry answers for any interval — and multiply n squared out for a realistic read length to show what that costs.
Demonstrate the decision under a real constraint: name the consumer that justifies the table, do the memory arithmetic per worker, and say at what input size you abandon both approaches.
Own the standard across the pipeline: which method is the default, what evidence would justify adopting a subtler linear algorithm, and how per-record memory is bounded so one outsized record cannot take a worker down.
## The two profiles, side by side | | Centre expansion | Interval table | |---|---|---| | Time for one longest run | O(n^2) worst case | O(n^2) | | Auxiliary space | O(1) | O(n^2) cells | | Answers "is i..j symmetric?" later | no, recompute | yes, constant time | | Allocation per record | none | one table per record | | Parallelism | trivially, per centre | per record only | | Handles the deletion variant | no | yes | The time column is the surprise for many candidates: the table is **not** faster. Both are quadratic. So the entire decision is about what else you need and what memory you can spend. ## Do the arithmetic before arguing Memory is the first thing to make concrete, because "O(n^2) space" is abstract until you multiply. - A 500-base read: 250,000 cells. Trivial. - A 5,000-base read: 25,000,000 cells. Already tens of megabytes per worker even at one byte per cell — and in a batch job that allocates one per record, the churn dominates the actual work. - A 100,000-base read: 10^10 cells. Impossible — but notice that O(n^2) *time* is 10^10 operations too, so the algorithm was already the wrong tool before memory decided it. That last line is the senior move. When someone proposes the table for very long inputs, the right response is not "it will not fit" but "neither method fits; the shape of the problem has to change". ## When the table genuinely earns its keep The table's product is not the longest run — it is **constant-time palindromicity for every interval**. Pay for it when something consumes that: 1. **An enclosing optimisation.** Splitting a read into the fewest symmetric segments is itself a DP whose transition asks "is the stretch from i to j symmetric?" for many pairs. Recomputing each with an expansion turns an O(n^2) job into something markedly worse; precomputing the table once makes each query free. 2. **Aggregate statistics.** Counting how many symmetric intervals a read contains, or histogramming them by length, touches every interval by definition, so there is nothing to save by being lazy. 3. **Repeated queries against one fixed read** — a reference sequence consulted by many later requests. Build once, amortise across queries. 4. **The deletion (subsequence) variant.** There is no centre to expand around when characters may be skipped, so a table is not a choice, it is the method. If none of these apply, the table is memory spent to produce a number that O(1) space would have produced just as fast. ## When centre expansion is clearly right One answer per record, records processed in a stream, workers with a fixed memory budget, and a desire to keep allocation out of the hot path. Expansion also degrades gracefully in a way the table does not: if the domain says markers are never longer than L bases, cap each expansion at width L and the cost falls to O(nL), effectively linear for small L. There is no analogous saving for a table that must exist in full before it is useful. ## Constraints beyond the asymptotics - **Maintainability.** A linear-time palindrome algorithm exists (Manacher's), and it is genuinely faster asymptotically, but it is subtle enough that few reviewers will confidently modify it a year later. On short reads its advantage is invisible. Choosing it needs a real measurement, not a preference for the better exponent. - **Small-n reality.** Asymptotic superiority promises nothing at the sizes you actually run. For a few hundred bases the constant factors and the absence of allocation dominate, which is another vote for expansion. - **Failure modes under load.** A per-record table makes memory usage a function of the *largest* record in the batch, so one unusually long read can take a worker down. Constant-space expansion has no such cliff — the run time grows, but nothing runs out. - **Reproducibility.** Whichever you pick, pin the tie-breaking rule for equal-length answers (leftmost, say). Two implementations that disagree on which of several equally long symmetric regions to report will produce diffs that look like data changes. ## How to answer this in an interview Refuse the framing that the table is the "real DP solution" and expansion is the trick. State that both are quadratic in time, that the table's product is reusable interval queries, and then name the specific consumer that would justify it in the scenario given. Add the memory arithmetic for the actual read length, and finish by saying at what size you would stop tuning the choice and change the approach.
- Give a concrete consumer that justifies building the table.A computation that splits a read into the fewest symmetric segments. Its transition repeatedly asks whether a given stretch is symmetric, for many pairs of endpoints. Precomputing the table makes every one of those queries constant time; recomputing with an expansion each time multiplies the cost of the outer optimisation.
- Reads are hundreds of thousands of bases. What changes?Both methods leave the table of options. O(n^2) time alone is around 10^10 operations, so memory is not the first wall. Either move to a linear-time palindrome algorithm, or exploit a domain bound — if markers cannot exceed L bases, cap expansion width at L for O(nL).
- Would you reach for the linear-time algorithm by default?No. It is asymptotically better but subtle enough that it becomes the code nobody wants to touch, and on short reads its advantage does not show up in measurements. Adopt it when profiling on real read lengths says the quadratic scan is the bottleneck, not on principle.
- Any operational hazard specific to the per-record table?Memory becomes a function of the longest record in the batch, not the average, so a single unusually long read can exhaust a worker. Constant-space expansion has no such cliff — it slows down instead of falling over, which is usually the preferable failure mode in a batch pipeline.
saying these in an interview costs you the question
- Believes the interval table is asymptotically faster
- Builds the table when only one answer is needed
- Ignores that memory scales with the longest record
- Assumes the table scales to very long reads
- Picks the linear-time algorithm without measuring