Data Structures That Win Interviews

Algorithm questions are usually data-structure questions in disguise: pick the right container and the algorithm writes itself. This lesson is the working inventory, organized by what question each structure answers.

Stack — "what did I see most recently?"

LIFO; $O(1)$ push/pop. The tell: problems about matching, nesting, or undoing. Balanced parentheses, undo history, expression evaluation, and the interview classic next greater element: scan the array keeping a stack of indices awaiting their answer — each element pushed and popped once, $O(n)$ despite the nested feel. Call stacks make recursion a stack too — which is why any recursion can be converted to iteration with an explicit one.

Queue and deque — "process in arrival order"

FIFO; $O(1)$ at both ends for a deque. The market-native example: limit order books match in price-time priority — each price level is literally a queue. Any simulation of fills, BFS traversal, or rate limiting (sliding-window counters) runs on one. The deque powers the elegant $O(n)$ sliding-window maximum (front holds the current max's index; smaller elements are evicted from the back) — a rolling-high-water-mark question quant screens love.

Heap — "give me the extreme, repeatedly"

A partially-ordered binary tree: $O(1)$ peek at min/max, $O(\log n)$ insert/pop. The tell: top-k or running extreme under a stream. Top 10 movers among 5,000 symbols streaming all day: a size-10 min-heap, $O(\log 10)$ per tick. Running median: the two-heap construction from the complexity lesson. Merging $k$ sorted feeds (timestamps from $k$ exchanges): a $k$-way heap merge, $O(n \log k)$.

Hash map / set — "have I seen this? what's it mapped to?"

$O(1)$ average lookup/insert; the single most used structure in interviews and in production. Two-sum, deduplication, caching, grouping, counting — the default answer to "can you do better than $O(n^2)$?" Costs worth naming: memory overhead, no ordering, and worst-case degradation (rare, but saying "average case" earns points).

Trees and sorted structures — "order matters, and it changes"

A balanced BST (or a skip list, or Python's sortedcontainers) keeps items sorted under inserts/deletes: $O(\log n)$ for insert, delete, predecessor/successor, and range queries. The canonical quant example again: the price levels of an order book — you need best bid (max), best ask (min), insertion of new levels, and removal of emptied ones, all fast, all while ordered. Hash maps can't do "nearest price"; heaps can't delete from the middle cheaply; the sorted structure does both.

Choosing under pressure

The question sounds like…	Reach for
matching / nesting / undo	stack
arrival order, sliding window	queue / deque
top-k, running min/max/median	heap
seen before? key → value	hash map / set
sorted order that keeps changing	balanced BST / sorted list
relationships / networks	graph + BFS/DFS

The interview version

"Design the data structures for a limit order book." — Two sorted structures (bids descending, asks ascending), each level holding a FIFO queue of orders, plus a hash map from order-id to its exact location for $O(1)$ cancels. That one sentence composes three structures, states why each is there, and is close to how real matching engines are described. Practice giving it — order-book design is the single most common quant-dev system question.