Blog · page 22
Notes on engineering, design, and everything in between.
Consistent hashing: why adding a machine does not reshuffle every key
Modulo sharding moves almost all data when the machine count changes. Put the hash space on a ring and let each key follow it clockwise to the first node, and only one arc moves. Virtual nodes are the price.
Winning at Gomoku: checking the last stone is enough
Rescanning the whole board after every move is waste. Only the newest stone can create a line, so four directions from that point settle it in constant time.
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.