Blog · page 8
Notes on engineering, design, and everything in between.
Sliding windows: decide what the window tracks before writing the loop
A window works when validity changes monotonically with its edges. Write down the tracked state and the shrink condition first, and the two-pointer loop amortises to O(n) on its own.
Monotonic stacks: next greater element in O(n), not O(n squared)
Each index is pushed and popped at most once, so what looks like a nested loop is linear. Recognise the first larger or smaller neighbour shape and the same template applies.
Counting the ones in a binary number: from loops to SWAR
Popcount has three forms: loop once per set bit, a lookup table, or SWAR across bit fields. They differ by orders of magnitude, and Rust and WebAssembly already expose it as a single instruction.
Union-find: two lines of optimisation make every operation near constant
Path compression flattens the tree, union by size stops it growing tall. You need both before the cost drops to the inverse Ackermann function, which is never above 5 in practice.
In Rust, context belongs on the line that actually fails
The question mark operator rethrows an error without saying which step failed. Structured errors in the core, Context in the application layer, with the input attached, is what makes a log line locatable.
When a crate should become a workspace
The trigger for splitting a workspace is build time and dependency boundaries, not tidy directories. Split when three signals hold, or you trade one compile for managing several packages.