Question 1

Two-sum on an unsorted array: a hash map is O(n) time and O(n) space; sorting and using two pointers is O(n log n) time and O(1) extra space. Which is right?

Accepted Answer

It depends which resource is scarce — one trades memory for time, the other trades time for memory. Both solutions are correct, so the question is really “which resource is scarce here?”. The hash map buys linear time with linear memory and keeps the original indices; the sort buys constant extra space with a log factor and loses them. Stating the trade and then asking which side the system cares about is the answer an interviewer is waiting for.

Question 2

Now the array arrives already sorted. Does the trade-off still exist?

Accepted Answer

No — two pointers is now O(n) time and O(1) space, so it dominates the hash map on both axes. A trade-off only exists while neither option dominates. With the input pre-sorted the two-pointer scan is linear time and constant space, so there is nothing left that the hash map does better. This is why “what are the givens?” comes before “which technique?” — sortedness in the statement is a resource the setter already paid for.

Question 3

The array is unsorted again, and now the two original indices must be returned. What does that constraint cost?

Accepted Answer

Either keep the hash map, or sort value-and-index pairs and spend O(n) space carrying the indices. Indices are data, and data that must survive a reordering has to be carried explicitly. Pairing each value with its index costs O(n) space, which is precisely what the sorting route was trying to avoid — so the constraint often pushes the answer back to the hash map. Noticing this before writing code is the difference between one solution and a rewrite.

Question 4

Adding a cache to naive recursive Fibonacci turns O(2ⁿ) into O(n). What exactly did that memory buy?

Accepted Answer

Each distinct argument is computed once, so the exponential tree collapses to n computations plus cheap stubs. There are only n distinct questions in the recursion — fib(0) through fib(n) — but the naive tree asks them exponentially many times. Storing n answers makes every repeat request return immediately, and the subtree beneath it is never built at all. In the recorded run of fib(7) the naive tree has 41 nodes and the memoized one has 13.

Question 5

You add a memo to merge sort’s recursive calls. What does the extra memory buy?

Accepted Answer

Nothing — every call receives a different range, so no cached answer is ever requested twice. Memoization needs overlapping subproblems, and divide-and-conquer without overlap is not dynamic programming. Merge sort splits into two disjoint halves, so it never asks the same question twice and the memo pays memory for zero hits. The quick diagnostic is distinct states against recursion-tree size: when they match, caching is dead weight.

Question 6

A knapsack table is n items by W capacities. When may you drop it to two rows, and what changes?

Accepted Answer

Whenever each row reads only the row above: space falls from O(nW) to O(W) and the time is unchanged. Each cell reads the cell directly above it and the cell up and to the left, both of which live in the previous row, so nothing older is ever consulted. Keeping two rows — or one row scanned in the right direction — cuts space from O(nW) to O(W) while performing identical arithmetic. It is the most reusable space optimization in dynamic programming, and edit distance and longest common subsequence qualify for exactly the same reason.

Question 7

You compress that table to two rows, and the interviewer asks which items were chosen. What now?

Accepted Answer

The compressed version cannot answer it — reconstruction needs the full table or a second pass to rebuild the path. Space compression throws away the history that reconstruction reads back. If the chosen items are required, you either keep the O(nW) table and walk it backwards, or use divide-and-conquer reconstruction to recover the path in O(W) space at the cost of a log factor in time. Volunteering that limitation as you propose the optimization is what makes it sound deliberate rather than lucky.

Question 8

Reversing an array in place versus building a reversed copy — what is actually being traded?

Accepted Answer

O(1) extra space against keeping the original intact for everyone else holding that reference. In-place is not only a space optimization — it is a decision about visibility, because every other reference to that array sees the change. A copy costs O(n) memory and leaves the input usable, which is what callers normally expect from a function that returns a value. When a routine mutates its argument, say so in the name or the documentation, because the trade is a contract as much as a cost.

Question 9

Merge sort spends O(n) on a buffer while quicksort spends O(log n) on its stack. What does the buffer buy?

Accepted Answer

A worst case equal to its average case, plus stability — neither of which quicksort offers. The buffer is the price of the guarantee: merging two adjacent sorted halves in place would overwrite elements that have not been read yet. What it buys is a bound that never degrades, plus stability, which is why library sorts for linked lists, external data and multi-key records are merge sorts. Quoting merge sort’s space as O(log n) because of the recursion is the classic way to undo an otherwise good answer.

Question 10

Counting sort runs in O(n + k) for keys drawn from a range of size k. When does that stop being a good deal?

Accepted Answer

When k dwarfs n — the counting array is O(k) memory whether or not those keys ever occur. The bound O(n + k) hides that k is memory as well as time, allocated for every possible key whether it appears or not. Sorting a thousand 64-bit integers this way would demand an impossible array, which is why counting sort is reserved for small dense key ranges — bytes, ages, grades. Radix sort is the standard escape: apply counting sort digit by digit so that k stays tiny.

Question 11

A prefix-sum array costs O(n) to build and O(n) to store. When is it worth building?

Accepted Answer

As soon as several range-sum queries are expected, since each query drops from O(n) to O(1). Precomputation is a trade you win only by amortising it: the O(n) build has to be repaid by the queries that follow. With q queries the choice is O(n·q) against O(n + q), so two or three queries already justify it and a query-heavy workload makes it obvious. If the array changes between queries, the honest answer is a Fenwick or segment tree, which keeps both operations logarithmic.

Question 12

A recursive function allocates no arrays whatsoever. What is its space complexity?

Accepted Answer

O(depth) — every unfinished call holds a frame containing its parameters and locals. Recursion depth is a space cost of O(depth) and a crash risk once the depth outruns a stack of a few megabytes. That is why the honest answer for a recursive DFS is O(V) space in the worst case, and why quicksort is quoted as O(log n) space rather than O(1). Giving time and space unprompted is the cheapest way to sound like you have done this before.

Question 13

A lookup table is built once, never changed, memory is tight, and range queries are needed. Hash map or sorted array?

Accepted Answer

Sorted array with binary search — compact, cache-friendly, and ranges fall straight out of the ordering. A hash map buys O(1) expected point lookups and pays with load-factor slack, per-entry overhead and no ordering at all. A sorted array is one contiguous block searched in log n probes, slower asymptotically and often faster in practice thanks to locality — and “everything between x and y” falls out for free. When the data is static, the hash map’s advantage on insertions is worth nothing.

Question 14

A linked list stores less per element than a vector, yet iterating it measures five times slower. Why?

Accepted Answer

Each node is a separate allocation, so nearly every step is a cache miss the vector never pays. Big-O ranks growth, and wall clocks also charge for memory layout. A vector’s elements sit side by side, so one cache line brings in several of them and the prefetcher predicts the next; a list pointer-chases into unrelated addresses and stalls on each hop. It is the same effect that makes heap sort lose to quicksort in practice despite matching bounds.

Question 15

A memoized function is no faster than the naive one, and its cache key is a serialised copy of the whole input array. What went wrong?

Accepted Answer

Building the key is O(n) per call, so the cache costs about as much as the work it saves. A cache pays only when the key is far cheaper than the computation it replaces. Serialising an n-element array on every call adds a linear cost to each of exponentially many calls, so the bottleneck is key construction rather than lookup. The fix is to key on the small state that actually distinguishes subproblems — a pair of indices, a remaining capacity — which is the same discipline as defining the DP state in words first.

Question 16

A graph traversal keeps a visited set costing O(V) memory. What does that memory guarantee?

Accepted Answer

That every node is expanded once, which is what makes the traversal terminate and stay O(V + E). Without the set, a cycle sends the traversal round forever and a dense graph re-explores the same subgraphs exponentially often. One bit per node converts that into a promise that each node is expanded exactly once and each edge inspected at most twice, which is where O(V + E) comes from. It is the cleanest case in this deck of memory buying a bound rather than buying speed.

Question 17

Explain to a colleague how you decide whether to spend memory to save time. Say it out loud before revealing.

Accepted Answer

I think of extra memory as buying a specific thing, and I make myself name it. A hash map buys me lookup, so it turns a nested pairwise scan into one pass — I pay n slots and get a factor of n back, which is almost always worth it. A memo buys me “I already answered this”, so it only pays when the recursion actually asks the same question twice: it collapses Fibonacci from exponential to linear, and it does nothing at all for merge sort, because the two halves are different ranges and no cached answer is ever requested. A precomputed table buys me repeat queries, so it repays itself from the second query onward and is a loss if there is only one. Then I ask what the system is short of. If memory is the binding constraint I go the other way and spend time instead — sort in place and use two pointers rather than a hash map, or roll a DP table down to two rows. The one thing I always say out loud is what the cheaper version gives up: the two-row table computes the same optimum but can no longer tell you which items were chosen, and that is usually the follow-up question.. A strong answer treats memory as a purchase with a named benefit, gives one case where it pays and one where it does not, and mentions the constraint that decides. The tell is that it ends in a question about the system rather than a rule.

Space and time trade-offs — every question, written out