Say “hash map lookup is O(1)” in an interview and a decent interviewer asks back, almost reflexively, “average or worst case?” It’s a small question that tells them whether you understand the structure or just memorized a row of a table. Most of the useful knowledge for a coding round lives in exactly these follow-ups: the amortized append that occasionally costs O(n), the “constant time” that degrades to linear under collisions, the balanced tree that hands you ordered iteration for free.
This is the reference I wish I’d had pinned to a second monitor during practice. Learn the table cold, then spend your effort on the cells that come with an asterisk, because those asterisks are where interviewers probe.
The operations table, and the cells that carry an asterisk
Read the average-case columns for how your code behaves in practice and the last column for what a follow-up question will target. Everything here assumes the standard library implementation you’d actually reach for: a dynamic array (Python list, Java ArrayList, C++ vector), a hash table (dict, HashMap, unordered_map), a balanced search tree (TreeMap, C++ std::map), and a binary heap.
| Data structure | Access by index or key | Search by value | Insert | Delete | What breaks the fast case |
|---|---|---|---|---|---|
| Dynamic array (list, vector) | O(1) | O(n) | O(1) amortized at the end; O(n) in the middle | O(n) | Growing past capacity copies every element |
| Hash map / hash set | O(1) average, O(n) worst | O(1) average, O(n) worst | O(1) average | O(1) average | Collisions or an adversarial hash send every key to one bucket |
| Balanced BST (TreeMap, std::map) | O(log n) | O(log n) | O(log n) | O(log n) | Nothing degrades it, but every operation pays the log factor |
| Binary heap | O(1) to read the min or max | O(n) | O(log n) push | O(log n) pop of the top | No way to find an arbitrary value faster than a full scan |
| Singly linked list | O(n) | O(n) | O(1) at a node you already hold | O(1) at a node you already hold | Reaching that node in the first place is O(n) |
| Stack / queue (array-backed or deque) | n/a | n/a | O(1) at one or both ends | O(1) at one or both ends | Only the ends are cheap; the middle is off-limits by design |
| Trie (prefix tree) | n/a | O(m) for a key of length m | O(m) | O(m) | Cost tracks key length, not the number of stored keys |
| Union-Find (disjoint set) | n/a | O(α(n)) find | O(α(n)) union | n/a | Near-constant only with path compression and union by rank |
α(n) there is the inverse Ackermann function, which stays below 5 for any input you will ever see, so treat union and find as effectively constant while being able to say why they technically aren’t.
Why append is O(1) amortized, not O(1)
A dynamic array keeps a backing buffer larger than its length. Appending drops the new element into the next open slot, one cheap write. When the buffer fills, the array allocates a bigger one, usually double the size, and copies every existing element across. That single append costs O(n).
So how is append O(1)? Count the total work across a long run of insertions. Doubling means the expensive copies happen at sizes 1, 2, 4, 8, 16, and so on. Sum those copies for n appends and it comes out to roughly 2n element moves total, which averages to a constant per append. That is what amortized means: no single call is guaranteed fast, but the cost spread over the sequence is. If someone asks for the worst-case single insertion, it’s O(n). If they ask for the cost of building an n-element list, it’s O(n) overall, or O(1) per element. Both answers are correct, and naming which one you’re giving is the whole point.
The constant time that isn’t
Hash maps are the structure people quote most confidently and understand least. Average-case O(1) holds when keys spread evenly across buckets and the load factor stays low, which standard libraries maintain by rehashing into a bigger table once occupancy crosses a threshold, around 0.75 in Java’s HashMap and in CPython’s dict. Rehashing is itself amortized O(1): occasional O(n) rebuilds averaged over many inserts.
The worst case shows up when keys collide. If every key lands in one bucket, lookup walks a chain of n entries and you’re back to O(n). This used to be a real attack: send a web server thousands of form fields whose keys all hash to the same bucket, and its dictionary operations degrade to quadratic, tying up the process. Two defenses are worth knowing, because interviewers at security-minded shops ask. CPython and others randomize the hash seed per process with SipHash, so an attacker can’t precompute colliding keys ahead of time. Java’s HashMap, since Java 8, converts a bucket to a red-black tree once it holds eight or more colliding entries and the table is large enough, capping that bucket’s worst case at O(log n) instead of O(n). Neither changes the average case you quote day to day, but knowing the failure mode is what separates a memorized answer from an understood one.
When the hash map is the wrong default
Hash maps win on raw lookup, so people reach for them by reflex and sometimes lose points for it. If the problem needs keys in sorted order, range queries like “all entries between 100 and 200,” or the next key above a given value, a balanced tree does each in O(log n) while a hash map forces an O(n log n) sort every time you want order. If you only need the minimum or maximum pulled repeatedly, a heap beats both. And if the keys are strings that share long prefixes, like autocomplete or routing tables, a trie can undercut a hash map on both time and memory because it never stores a shared prefix twice. Picking the structure that matches the access pattern, rather than the one with the best headline complexity, is most of what a data-structure question actually tests.
Reading the problem for the structure it wants
Half of interview speed is matching a problem’s shape to the structure or pattern that fits before you write anything. A sorted array plus a target sum points at two pointers moving inward. A contiguous subarray or substring with a constraint that tightens and loosens as you scan is a sliding window. “Top k” or “kth largest” wants a heap of size k, which gets you O(n log k) instead of sorting everything at O(n log n). “Next greater element” or “days until a warmer temperature” is a monotonic stack. Grouping connected things, or answering “are these two in the same set,” is union-find. Anything on a grid or graph asking for the shortest unweighted distance is BFS; asking only whether a path exists, or exploring fully, is DFS. A search space that is sorted or monotonic, even implicitly, invites binary search, including binary search on the answer for “minimum capacity to ship packages in D days” style problems.
Recognizing the pattern also hands you the complexity for free. Once you’ve said “size-k heap,” O(n log k) follows without deriving anything. That is the real value of drilling patterns, not the templates but the reflex that reads a prompt and narrows a hundred approaches down to two.
How to say it so nobody corrects you
State the operation, the case, and the variable. “Building the frequency map is O(n) over the n characters.” “Popping from the heap k times is O(k log n).” Name the variables when there is more than one, because O(nm) for an n-by-m grid reads as sloppy if you never said what n and m are. Give amortized and worst case separately when they differ, and say which one the interviewer probably cares about. Space counts too, and it’s the piece people forget: a recursion lives on the call stack, so a depth-d recursion is O(d) space even when it allocates nothing else, and a clever memo table can quietly cost O(n^2).
The questions that surface all of this are short and predictable:
- “Average or worst case?” after any hash-based answer
- “What’s the space complexity, including the call stack?”
- “Can you do better than O(n log n) here?” which is usually the hint that a hash map or a counting sort collapses it to O(n)
- “What happens if the input is already sorted, all identical, or adversarial?”
Rehearse the answers to those four until they come out flat and automatic, and a chunk of the round stops being a test at all.
The table is worth memorizing cold, but the asterisked cells are where a round is won or lost. Anyone can say O(1). The person who gets the offer is the one who, without pausing, adds “average case, worst case O(n) under collisions, and here’s exactly when that bites.”
Drill the patterns next:
