Most algorithm interviews are not a memory test. The interviewer already knows what a hash table is; what they want to see is whether you can reason about cost, pick between two reasonable options and say why. These fifteen come up constantly. For each one, what is actually being tested, and the answer that lands.
Complexity
1. What does O(n log n) actually mean? It describes how the running time grows as the input grows, ignoring constants and lower-order terms. It says nothing about speed on a given machine: an O(n²) algorithm with a tight inner loop can beat an O(n log n) one for n = 50. The right answer mentions both halves — the growth rate, and the fact that constants matter at small n. Interviewers are listening for the second half.
2. What is the difference between O, Ω and Θ? Big-O is an upper bound ("no worse than"), Big-Omega a lower bound ("at least"), Big-Theta both at once ("exactly this growth"). Insertion sort is O(n²) and Ω(n) — quadratic at worst, linear on already-sorted input — so it is not Θ of anything single. In practice people say "O" when they mean Θ; it is worth saying the precise thing once and then relaxing.
3. How do you work out the complexity of a loop you have just written? Count how many times the innermost statement runs as a function of n. Nested loops that each run n times give n². A loop that halves the range each pass gives log n. A loop inside a halving loop gives n log n. Recursive functions need the recurrence: mergesort splits into two halves and does linear work merging, T(n) = 2T(n/2) + O(n), which is n log n.
4. What is amortised complexity? The average cost per operation across a sequence, when one occasional operation is expensive. Appending to a dynamic array is O(1) amortised: most appends are free, and the rare doubling-and-copy costs O(n) but happens so seldom that the average stays constant. Saying "amortised O(1), worst case O(n)" is more accurate than "O(1)" and interviewers notice.
Data structures
5. Array or linked list? Arrays give O(1) access by index and sit in contiguous memory, so they are cache-friendly — which in real code often matters more than the theory. Linked lists give O(1) insertion and removal if you already hold the node, which is the clause people forget: finding the node first is O(n). Most of the time, the array wins.
6. Why is a hash table O(1) on average but O(n) in the worst case? Because the worst case is every key colliding into one bucket, which degrades the lookup to a linear scan of that bucket. Good hash functions and resizing keep the load factor low so that does not happen. If the interviewer pushes, mention that some languages now randomise their hash seed specifically so an attacker cannot craft colliding keys and turn your lookup into a denial of service.
7. Stack or queue — give me a real use for each. A stack for anything that must unwind in reverse: undo history, the call stack itself, matching brackets in a parser. A queue for anything served in arrival order: a print spooler, a job queue, breadth-first search. Answering with a concrete system rather than "LIFO and FIFO" is the whole point of the question.
Sorting and searching
8. Quicksort or mergesort? Both are O(n log n) on average, and mergesort is O(n log n) in the worst case where quicksort is O(n²). Yet quicksort usually wins in practice because it sorts in place with a small constant and good locality, while mergesort needs O(n) extra space. Use mergesort when you need stability or predictable worst-case behaviour, or when you are sorting a linked list. Most standard libraries ship a hybrid — introsort, which starts as quicksort and falls back to heapsort when recursion goes too deep.
9. What does it mean for a sort to be stable, and when do you care? A stable sort keeps equal elements in their original relative order. You care whenever you sort by one key and then another: sort by name, then stably by department, and inside each department the names are still alphabetical. Mergesort is stable; quicksort as usually written is not.
10. Write binary search. Two preconditions the interviewer wants to hear before you write anything: the collection must be sorted, and you must have random access, which rules out a linked list. Then the bug almost everyone writes:
mid = (low + high) / 2; // overflows when low + high exceeds the integer limit
mid = low + (high - low) / 2; // does notThat overflow sat in Java's standard library for more than nine years, until Joshua Bloch wrote it up in June 2006. Mentioning it is a cheap way to show you have thought about the edges.
Graphs and recursion
11. Breadth-first or depth-first? BFS explores level by level using a queue, and on an unweighted graph the first time it reaches a node, it has found the shortest path there. DFS goes deep using a stack or recursion and is the natural fit for cycle detection, topological sorting and exhausting a search space. Both are O(V + E). If the graph is deep, DFS by recursion risks a stack overflow — say so.
12. Recursion or a loop? They are equivalent in power; the difference is the call stack. Recursion is clearer for anything tree-shaped, and unreadable for anything else. Every recursive call costs a stack frame, so depth is bounded — a recursive function walking a million-node list will crash where a loop will not. Tail recursion can be optimised into a loop, but PHP, Python and JavaScript do not do that, so in those languages the limit is real.
13. How do you detect a cycle in a linked list without extra memory? Floyd's algorithm: two pointers, one moving a step at a time, one moving two. If there is a cycle they eventually land on the same node; if the fast pointer reaches the end, there is not. O(n) time, O(1) space. The obvious alternative — a set of visited nodes — is also O(n) time but O(n) space, and saying that out loud shows you compared them rather than recalled one.
Dynamic programming and trade-offs
14. What is dynamic programming, and how do memoisation and tabulation differ? It is solving a problem by solving overlapping subproblems once and reusing the answers. Memoisation is top-down: write the recursion, then cache results as they are computed. Tabulation is bottom-up: fill a table from the smallest subproblem upwards, no recursion, no stack limit. Naive Fibonacci is O(2ⁿ); either technique makes it O(n). The follow-up question is usually space — Fibonacci by tabulation needs only the last two values, so O(1) space, and spotting that is the real answer.
15. When would you deliberately choose the slower algorithm? More often than the theory suggests. When n is small and always will be. When the faster one needs memory the machine does not have. When the slower one is ten lines and the faster one is two hundred that nobody on the team can maintain. When the data is nearly sorted and insertion sort's best case beats everything. An interviewer asking this wants to know whether you optimise for the machine or for the problem in front of you.
How to answer any of them
The pattern that works: restate the problem in your own words, say the brute-force approach and its cost out loud, then improve it and name the trade-off you just made. Talk while you think — an interviewer cannot score silence. And if you do not know, say what you would look up and why; that answer is worth more than a confident wrong one.