Study notes for contest and interview algorithms, starting from one map.
This section follows my second pass through algorithms: partly for the coding rounds of HFT and tech interviews, partly for contests, where the mathematics problems in the second half of a contest are mine. Start with the map; each block gets a post here once it is covered.
Click the map for the interactive version: click a box to see what it solves and when to reach for it; the buttons above it step through learning routes.
All four topics in this round answer queries on an array, and all of them bring brute-force $O(n^2)$ down. Two properties make that possible: monotonicity (binary search, two pointers) and accumulated quantities that can be …
In the mathematics problems of the second half of a contest, the hard part is rarely the theorem itself. Most theorems can be memorised; what goes wrong is not seeing which one a problem needs, or seeing it and failing to derive a …
Given $n$ numbers, pick any subset and XOR it together: what is the largest result? With $n = 50$ there are $2^{50}$ subsets, too many to enumerate. But the subset XORs repeat a lot. With three numbers $a$, $b$, $a \oplus b$, the …
