map / coding
Pillar 04 · 6 principles
Coding.
Practical code, under real constraints.
SRE coding rounds look less like puzzles and more like the job: parse this, limit that, cache the other — correctly, under concurrency, with sensible complexity.
Complexity from first principles
Big-O is just counting how work grows with input — and at production scale, the difference between n and n² is the difference between fine and down.
Operation counts for n, n log n, and n² racing as input grows.
Core data structures
Hash maps, heaps, and tries each trade memory and ordering for a specific fast operation; pick the structure by the operation you need most.
Step-through inserts and lookups in a hash map, a heap, and a trie.
Concurrency & races
A race happens when correctness depends on the interleaving of operations you don’t control.
Two threads incrementing a counter on a shared timeline, losing an update.
Log parsing
Stream the input, keep only the state you need, and you can process logs far larger than memory.
Lines flowing through a parser into a bounded top-k structure.
Rate limiters
A token bucket allows bursts up to its size while enforcing a long-run average rate.
A bucket refilling at a fixed rate as requests drain it.
LRU cache
A hash map plus a doubly linked list gives O(1) lookup and O(1) eviction of the least recently used entry.
Get/put operations reordering a linked list while the map points into it.
How it shows up in interviews
- “Parse this log and report the top offenders.”
- “Build a rate limiter.” “Build an LRU cache.”
- Spotting and fixing a race condition.