Arrays & Strings

One append is usually constant time, but the append that finds the buffer full is O(n): it allocates a larger block and copies every buffered character across. Amortized over many appends the total is still O(n).

Swapping code units also flips the internal order of multi-unit characters: a surrogate pair comes out low half first and becomes invalid, and a combining accent lands before the letter it belonged to. Correct order-reversal walks grapheme clusters.

Memory is fetched in whole cache lines, not single values. A 16-element stride over 4-byte values lands on a new line every step, exactly as many lines as the full scan touches, so traffic is unchanged and only the arithmetic gets cheaper.

Only when the array's order carries no meaning. Swapping the last element into the vacated slot is constant time but permutes the array; shifting the tail left costs Θ(n − i) and is the only order-preserving option.

Equal hashes do not mean equal text. The hash compresses m symbols into one bounded value, so different windows can collide. Rabin-Karp treats a hash match as a candidate only and confirms it with an O(m) comparison.

Odd-length symmetric spans center on a character; even-length spans center between two characters. That is n on-character centers plus n-1 gaps, so 2n-1 in total, and scanning only the n characters misses every even-length span.

Pre-allocating removes the repeated allocate-copy-release cycles during the load: fewer allocator round-trips, no moment holding two blocks at once, no growth-driven invalidation, and a flatter latency profile. It does not change the asymptotic cost of appending n elements.

Amortized O(1) bounds the total cost of a run of appends, not any single one. The appends that trigger growth copy the whole buffer, and those copies get slower as it grows — exactly the rare stalls a p99 measures.

Swap-with-last removal teleports the final live element into the hole, destroying the relative order of what remains. It is wrong whenever a consumer depends on that order — an arrival-ordered log, or any downstream search assuming sortedness.

One flat buffer wins when whole-grid passes dominate: a single allocation, contiguous scans, no per-access indirection. Separate row arrays win when the structure changes at row granularity — reordering, inserting or sharing rows costs a handle move instead of copying every cell.

Summing the fragment lengths first lets you allocate the result exactly once and fill it in one pass: no reallocation copies, no slack, no growth pause. A growable buffer ties asymptotically but loses on peak memory and tail latency.

Bytes are fixed size, so byte N is one address computation away. Characters are not: UTF-8 spends one to four bytes each, so reaching the Nth character means scanning from a known boundary — O(n) unless you keep an index.

Interning keeps one canonical instance per distinct value, so it pays when cardinality is small and bounded while occurrences are enormous. It backfires on high-cardinality fields: the table retains every distinct value forever, turning short-lived garbage into a permanent leak.

A fixed-capacity contiguous buffer gives a provable memory budget, no allocation in the hot path, and O(1) indexing — exactly what a constrained device needs. The hardware claim is false: memory protection is page-granular, so most out-of-bounds accesses land in mapped memory and trap nothing.

Each insert opens a hole mid-array, so it costs linear time in the scores already stored. Across m events that compounds to quadratic total work — invisible at fifty players, a stall at fifty thousand.

On varied text with short patterns a naive scan already runs close to linear with a tighter inner loop, so KMP's table build and extra memory rarely pay off. Pay for it when inputs are repetitive or attacker-chosen.

Any input that makes a fingerprint hit fire at nearly every offset forces an O(m) confirmation each time, giving O(n*m). Either an attacker crafts collisions against your fixed hash parameters, or the pattern genuinely occurs almost everywhere.

State the canonicalization first: case folding, whether whitespace and punctuation are dropped, whether digits count, and which characters are in scope at all. Two phrases are anagrams only relative to that rule, so leaving it unstated leaves the behaviour undefined.

Decide on the transient peak, not the copy count. Both blocks are live during a growth, so 2x peaks near three times the data and 1.5x near two and a half; factors under about 1.618 also permit reuse of freed blocks.

Often not. The cheapest rotation of a huge log is logical: keep a base offset and index modulo n, moving nothing. A physical in-place rotation saves memory but rewrites every page and is not crash-safe.

Ask first whether the original must survive and whether the board is square: those two answers usually decide it outright. Only when peak memory is genuinely the binding constraint is the harder in-place ring cycle worth its review cost, and transpose-plus-reverse is already in-place anyway.

Anything that treats one row's length as the table's width: column reads, per-column aggregates, transposition, and neighbour lookups. A jagged table has no single column count, so those operations either read past a short row or quietly ignore the tail of a long one.

Copy the record once into a mutable character array, overwrite the digits in place at O(1) each, then convert back once. That is two copies per record instead of one full copy per masked character.

Both are O(n) time and O(1) extra space, so asymptotics cannot separate them. Juggling halves the writes but strides through memory in gcd-sized cycles, and those scattered touches cost more than the extra sequential pass reversal pays for.

A substring can be a view — an offset and length over the parent's buffer — rather than a copy. Extraction is then O(1), but the view references the whole parent buffer, so all 2 GB stays reachable while the slice lives.

One array per field means a loop reading a single field gets only that field's values in each fetched cache line, instead of dragging along every unused field of every record. Fewer lines touched, far less wasted bandwidth, same O(n).

KMP's whole state is the prefix table plus the current matched length, and its text pointer never moves backward, so it consumes each byte once, in order, with memory proportional to the signature and a work bound hostile traffic cannot inflate.

It depends on whether holding the December peak actually costs you anything measurable. Shrinking copies survivors into a smaller block and invalidates positions, so any automatic policy needs hysteresis: shrink only far below capacity, and to a size that leaves headroom.

One 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.