Write the regular-expression engine behind Sieve Mail's filter rules: a parser, Thompson's NFA construction and a simulation that runs in linear time, so no rule can hang the mail servers.
Parse and simulate
Literals, any character, *, +, ?, alternation and groups, compiled to an NFA and matched in linear time.
Classes, escapes and search
[a-z], [^0-9], \d, \w, \s, escaped punctuation, and finding a match anywhere in the text.
Counted repetition
Support a{2,5}, a{3} and a{2,} without letting a{1000}{1000} blow up memory.
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.
Model order statuses, CSV quoting and regex matching as state machines: one transition table, guards for business rules, event logs you can replay, and NFAs that track several states.
How to parse formulas, JSON and patterns by hand: split input into tokens, write the grammar down, turn each rule into a function, handle precedence, and report exact error positions.