Data Structures

When you insert and remove in the middle far more often than you read by position.

An array gives you element 5,000 instantly but inserting at the front shifts everything. A linked list inserts anywhere in constant time once you are holding the node, but finding element 5,000 means walking 5,000 links. In practice arrays win more often than theory suggests, because walking contiguous memory is enormously faster than chasing pointers.

What it is really testing. Whether you know the cache answer. Almost everybody gives the textbook comparison; the candidate who mentions locality has used a profiler.

Because the key is turned into an index arithmetically, so nothing is searched.

Hashing the key produces a number, that number picks a bucket, and the bucket is reached directly. No comparison with the other entries happens at all. It is O(1) on average rather than always - a bad hash that puts everything in one bucket degrades to a linear scan.

What it is really testing. Whether you say "on average". The unqualified "it is O(1)" is the answer that invites the collision follow-up, which is the next question.

The collision is resolved, usually by chaining the entries in that bucket or by probing for the next free slot.

Chaining keeps a small list per bucket and walks it, comparing keys. Open addressing puts the entry in the next free slot by a fixed rule. Either way the key itself is still compared - hashing narrows the search, it does not replace the check, which is why keys must implement equality consistently with their hash.

What it is really testing. Whether you understand that the hash is a shortcut and not an identity. The "equal objects must have equal hashes" rule follows from this and is the usual follow-up.

A stack for undo and for call frames; a queue for jobs waiting their turn.

A stack is last in, first out: the most recent thing is the one you need back first, which is exactly undo, bracket matching, and the call stack itself. A queue is first in, first out: print jobs, request handling, breadth-first search. If you can name where each one appears inside the machine you are already ahead.

What it is really testing. Whether the definitions are attached to anything. "LIFO and FIFO" with no example is the answer of somebody who read it last night.

A tree where everything left of a node is smaller and everything right is larger - and sorted input ruins it.

The ordering is what makes lookup O(log n): at each node you discard half the remaining tree. Insert already-sorted data and every node goes to the right, so the tree becomes a linked list and lookup becomes O(n). That failure is why self-balancing trees exist.

What it is really testing. Whether you know the worst case. A candidate who only knows O(log n) has not thought about what the structure depends on.

A guaranteed O(log n) height, no matter what order the data arrives in.

Red-black and AVL trees do extra work on insert - rotations - to keep the height bounded. You pay a little on every write to remove the catastrophic worst case on every read. That is the trade, and naming it as a trade is the answer.

What it is really testing. Whether you can describe a cost as a trade rather than as a feature. You are not expected to code a rotation.

Getting the smallest or largest item repeatedly, without keeping everything sorted.

A heap gives you the minimum in O(1) and removes it in O(log n), but it does not keep the rest in order - which is exactly why it is cheaper than a sorted list. Priority queues, schedulers, Dijkstra, and "top k of a billion items" all run on one.

What it is really testing. Whether you reach for it in the "top k" problem. That is the question it is usually a setup for.

An adjacency list for most graphs, an adjacency matrix when the graph is dense or you need instant edge lookup.

A list stores, for each node, the nodes it points to: memory proportional to the edges, which real graphs have few of. A matrix is a grid of every node against every other: O(n squared) memory always, but "is there an edge from A to B" is one lookup. Social graphs use lists; small dense graphs use matrices.

What it is really testing. Whether you ask how dense the graph is before choosing. That question is a better answer than either structure.

O(1) amortised - usually instant, occasionally a full copy when it has to grow.

When the backing array is full the implementation allocates a bigger one, typically double, and copies everything over. That single append is O(n), but because the size doubles, those copies get rarer as the list grows, and the average works out to constant. "Amortised" is the word being fished for.

What it is really testing. The word amortised, and whether you can explain it rather than just say it. This is a favourite because the honest answer has a caveat in it.

When you only care whether something is present, and duplicates are meaningless.

The practical difference is the membership test: "is x in here" is O(1) in a hash set and O(n) in a list. Swapping a list for a set is the most common single fix for an accidentally quadratic loop, which is why this question comes up in code-review form.

What it is really testing. Whether you spot the quadratic loop. Expect a snippet with a list lookup inside a for loop and the question "can you make this faster?"

Prefix work - autocomplete, and finding every word starting with "pre".

A trie stores characters along the edges, so all words sharing a prefix share a path. Lookup costs the length of the word rather than depending on how many words are stored. A hash set can tell you a word exists; it cannot hand you every word beginning with "pre" without scanning all of them.

What it is really testing. Whether you can say what a hash set cannot do. That contrast is the reason the structure exists.

A shallow copy duplicates the container and shares what is inside; a deep copy duplicates all the way down.

Copy a list of objects shallowly and you get a new list pointing at the same objects - change one through either list and both see it. That is the bug: it looks correct in testing with numbers and strings, because those are usually immutable, and breaks the moment the elements are mutable.

What it is really testing. Whether you have had the bug. The giveaway is a candidate who can define both and does not sound like they have ever been caught by one.