Project: audit streaming palindromes, range caps, quantiles, and window order

Acceptance trace

Append abacaba and verify seven distinct nonempty palindromes, longest length seven, and propagated occurrence totals. Cap readings 47, 19, 83, 61, 29, 103 in positions one through four at 47 and verify total 292. In the frozen alert stream, the third smallest value in positions one through five is 47 and the first five positions contain two copies of 47. Compose calibrations (2,19), (3,7), (5,11), remove the oldest, append (7,23), and verify the transform changes from (30,40) to (8,54). All windows are half-open.

Failure and cost review

Test random text prefixes against a direct set of palindromic substrings, cap/sum sequences against a plain list, matrix ranks against sorted slices, and aggregate queues against left-to-right function composition. Include repeated characters, negative capacities, duplicate alert levels, and an empty queue. Count query rebuilds separately from mutation work: a matrix edit requires a new snapshot, while a palindromic append changes at most one distinct node. Record the worst observed cap-node visits and transfer length without advertising them as strict logarithmic bounds. A code result that matches one trace is insufficient if its hidden maximum or stack order invariant is already corrupt.

Common Mistakes

• Do not treat a raw palindrome end count as all occurrences.
• Do not cap a mixed segment without checking its second maximum.
• Do not deduplicate a wavelet matrix input stream.
• Do not swap calibration operands when composition is noncommutative.

Connected lessons

• Palindromic trees: index distinct palindromes as text arrives
• Segment tree beats: cap a range while retaining its sum
• Wavelet matrices: count frequencies and find subarray quantiles
• Two-stack window aggregation: keep FIFO order under a monoid
• Projects
• Quizzes
• Data Structures