Choosing a Data Structure

Almost every "which data structure" question reduces to one prior question: what operation must be fast?

Hash map — O(1) average lookup, insert, and delete by exact key, with no ordering. The default when you need to answer "have I seen this?" or "what is associated with this key?"

Balanced tree / sorted map — O(log n) operations and ordering, so it supports range queries, floor and ceiling lookups, and in-order traversal. Choose it over a hash map the moment you need "all keys between X and Y" or "the next key after X."

Heap — O(1) peek at the minimum or maximum, O(log n) insert and extract. Correct whenever you repeatedly need the extreme element without needing the rest sorted. "Top k of a stream" is a heap of size k, at O(n log k) instead of sorting everything at O(n log n).

Deque — O(1) insertion and removal at both ends. Sliding window problems are usually a deque holding indices.

Trie — prefix lookup in time proportional to key length rather than dictionary size. Autocomplete and prefix matching.

Union-find — near-constant merging and connectivity checks over disjoint sets. Connected components and cycle detection in an undirected graph.

Do not skip the plain array. A contiguous array is the fastest thing on real hardware for anything you scan, because the values sit next to one another and the prefetcher stays ahead of you. Asymptotic analysis assumes every memory access costs the same, which stopped being true decades ago, so a linear scan of a small array routinely beats the hash map or linked list that should have won — often up to a few hundred elements. Where two candidates share a complexity, prefer the contiguous one.

The interesting structures are usually two simple ones joined at the operation each is good at. An LRU cache is a hash map for lookup plus a doubly linked list for recency; a top-k over a stream is a heap plus whatever holds the stream. So when no single structure has every operation you need fast, that is a signal to compose rather than to compromise on the one you already know.

The interview move is to state the requirement first: "I need the minimum repeatedly and I don't need full ordering, so a heap." That sentence is worth more than the name alone, because it shows the choice was derived rather than recalled.