Data Structures and Algorithms: Index

Software engineering interviews at quant firms and frontier labs converge on one format. You get a class to build. It holds some state, it exposes a few methods, and once it works the interviewer adds a constraint and you extend what you already wrote. Not a puzzle with a single trick, and not a fresh problem each round.

That format runs on a small set of primitives. A hash map paired with a list. A heap you never delete from the middle. A deque you push and pop at both ends. Binary search on something that isn’t a list. The problems are endless and the primitives are not.

So this folder is the primitives, one page each, and every page does the same three things: what the structure or technique is, the canonical case typed out in full, and the mistakes I actually made writing it.

Canonical case only. Each page implements the most boring possible version. Binary search finds a value in a sorted list. Sliding window counts events in the last minute. Nothing clever, nothing generalized. The complexity belongs in the problems you solve with these, not in the primitives themselves, and once the primitive is automatic the variations come out on the spot.

Practical, not theoretical. No proofs, no derivations of why a heap is logarithmic. The assumption is you already know what these things are and when to reach for them. What you can’t do yet is type them cold, under a clock, with someone watching. That’s the gap this closes.

Structures come first, since a technique you can’t implement on a structure you don’t know is two gaps at once.

Index

• Dicts, defaultdict and Counter. O(1) lookup by key, and the two standard-library variants worth reaching for: defaultdict for dicts of containers, Counter for frequencies.
• Binary Search. Finding a position in something sorted, in O(log n). The convention that kills the off-by-one bugs, plus the boundary variants and which bisect call answers which question.
• Heaps. Cheapest access to the largest or smallest thing, when items keep arriving. Max-heaps in Python, top-k, and lazy deletion.
• Deques and Expiring Windows. Things arrive over time and old things stop mattering. O(1) at both ends, the expiry loop, and the amortized argument that makes lazy cleanup affordable. Not the two-pointer kind of sliding window.
• Tries. Prefix questions over a fixed set of keys. Nested dicts, the terminal marker, the recursive collector, and splitting on segments rather than characters.
• Dictionary compositions. A dict cannot compare its entries to each other. Three axes you might want to compare on, and the structure you bolt on to restore each one.
• Graphs and traversal. One loop, and the container decides the algorithm. Adjacency lists, BFS, DFS, uniform-cost search, and topological sort as the case with no start node.