Algorithms

How the running time grows as the input grows, ignoring constants and smaller terms.

It is about growth, not speed. An O(n) algorithm can easily be slower than an O(n squared) one on small inputs, because the constants it drops can be large. What it tells you is what happens when the input gets big - which is the only thing that survives a change of machine.

What it is really testing. Whether you know what it ignores. The candidate who says "O(1) means fast" has the wrong model and will pick the wrong structure later.

Halve the range by comparing with the middle element - and it only works if the data is already sorted.

Each comparison throws away half of what is left, so n elements take log2(n) steps: a million becomes twenty. The precondition is the whole story, because sorting first costs O(n log n) - so searching once is cheaper linearly, and sorting pays off only if you will search many times.

What it is really testing. Whether you volunteer "if it is sorted" without being prompted, and whether you spot that sorting-to-search-once is a bad trade.

Quicksort is usually faster in memory; mergesort is predictable and stable.

Both average O(n log n). Quicksort sorts in place with very little extra memory and has excellent cache behaviour, but its worst case is O(n squared) on a bad pivot. Mergesort guarantees O(n log n) always and is stable, at the cost of O(n) extra space - which is why it is the one used for linked lists and for external sorting.

What it is really testing. Whether you mention memory and stability, not just the average case. Both are O(n log n), so the average case cannot be the answer.

A stable sort keeps equal elements in their original relative order, which matters whenever you sort twice.

Sort a table by name, then by department. With a stable sort, rows within each department are still in name order - you have built a two-key sort out of two one-key sorts. With an unstable sort the first pass is destroyed, and the bug looks random.

What it is really testing. Whether you can give the two-pass example. It is the only reason anybody cares about stability, so an answer without it is a definition and nothing more.

BFS when you want the shortest path in an unweighted graph; DFS when you want to explore or recurse deeply.

BFS visits everything one step away, then two, so the first time it reaches the target it has taken the fewest edges. It needs a queue and holds a whole level in memory. DFS goes as deep as it can first, needs only the current path, and is natural for cycle detection, topological sort and exhausting possibilities.

What it is really testing. Whether you say "shortest path, unweighted". Dropping "unweighted" is the common slip - with weights you need Dijkstra, and that is the follow-up.

Solving a problem by solving its smaller overlapping subproblems once and remembering the results.

The word that matters is overlapping. Plain recursion on Fibonacci recomputes fib(30) thousands of times; storing each result as you go turns exponential into linear. Memoisation is top-down - recurse and cache. Tabulation is bottom-up - fill a table in order. Same idea, two directions.

What it is really testing. Whether you can say when it applies. DP is not "use a table"; it needs overlapping subproblems and optimal substructure, and saying so is the answer.

A stack frame per call - so depth costs memory, and too much depth overflows.

Every call keeps its own locals and return address until it finishes. Recursing a million deep will exhaust the stack in most languages, which an equivalent loop would not. Tail-call optimisation removes the cost in some languages and not in others - Python and Java do not have it.

What it is really testing. Whether you think about memory at all. Many candidates discuss recursion purely as elegance and are surprised by "what happens with a million items?"

It takes the best-looking option at each step, and it fails whenever a locally good choice rules out a better whole.

Greedy works for coin change in normal currencies and breaks for contrived ones: with coins 1, 3 and 4, making 6 greedily takes 4+1+1 - three coins - when 3+3 would do. Greedy is only provably correct when the problem has the right structure; otherwise it is a heuristic, and calling it one is the honest answer.

What it is really testing. Whether you have a counterexample ready. "It can be suboptimal" is weak; a specific failing case is the answer that lands.

Walk it once with a hash set - O(n) time, O(n) space - or sort first if you may not use extra memory.

The set answer is the expected one. The interesting part is the follow-up: "what if you cannot allocate?" - then sort and check neighbours, O(n log n) time and no extra space. If the values are known to be 1..n there is a cycle-detection answer in O(n) time and O(1) space.

What it is really testing. Whether you offer the trade before being asked. Giving both answers with their costs is the whole point of the question.

Walking a sorted sequence from both ends, moving whichever pointer can improve the result.

For "find two numbers that sum to a target" in a sorted array: if the pair sums too low, move the left pointer right; too high, move the right pointer left. That turns the obvious O(n squared) double loop into a single O(n) pass. The sliding window is the same idea for subarrays.

What it is really testing. Pattern recognition. This is one of perhaps six techniques that cover most array questions asked at this level.

Two pointers, one moving one step and one moving two - if they ever meet, there is a cycle.

Known as the tortoise and hare. If the list ends, the fast pointer reaches null and there is no cycle. If there is a loop, the fast pointer eventually laps the slow one inside it. It costs O(n) time and no extra memory, which is what makes it better than the obvious hash-set answer.

What it is really testing. Whether you give the O(1)-space version. The hash-set answer is correct and is the one the question is designed to improve on.

Caching - any lookup table that turns a recomputation into a read.

A hash index on a database column, a memo table in dynamic programming, or precomputed prefix sums that answer "sum between i and j" in O(1) instead of O(n). The trade runs both ways: compression spends time to save space, which is a good second example to offer.

What it is really testing. Whether you can produce a concrete example quickly. The question is a gift - it is checking that your vocabulary is attached to real code.