Complexity & how to run the coding interview

Explain Big-O, and the difference between O, Θ and Ω.

Big-O is an upper bound on growth as input size grows; Ω is a lower bound; Θ is both (a tight bound). In interviews people say "O" when they mean Θ, and that is fine — but knowing the distinction is a cheap way to sound precise.

Two more distinctions worth having ready:

• Best / average / worst case is separate from O/Ω/Θ. Quicksort is Θ(n log n) average and Θ(n²) worst; those are different cases, not different bound types.
• Amortised complexity averages over a sequence: a dynamic array's append is O(n) when it resizes, but O(1) amortised because doubling makes resizes exponentially rare.

Drop constants and lower-order terms — 3n² + 100n + 5 is O(n²) — but say when constants matter in practice: an O(n log n) algorithm with a huge constant can lose to O(n²) on n = 50, and cache locality routinely makes an array beat a "better" linked structure.

How do you determine the complexity of a recursive function?

Count the recursion tree, or use the Master Theorem for T(n) = a·T(n/b) + f(n):

• Merge sort: 2T(n/2) + O(n) → O(n log n).
• Binary search: T(n/2) + O(1) → O(log n).
• Naive Fibonacci: T(n-1) + T(n-2) → O(2^n); with memoisation, O(n).
• Subsets: two branches per element, n levels → O(2^n); permutations → O(n!).

Do not forget space: recursion costs O(depth) stack even when it allocates nothing else, which is why a recursive DFS on a 10^6-node path overflows and an explicit stack does not.

What are the complexities of the built-in data structures?

* average; worst case O(n) with adversarial collisions.

Python specifics people get wrong: list.pop(0) and list.insert(0, x) are O(n) (use deque); x in list is O(n); string concatenation in a loop is O(n²); slicing copies, so s[1:] in a recursion makes it O(n²); sorted() is Timsort, O(n log n) and stable, and near O(n) on partly sorted data.

How do you run the 45-minute coding interview?

A script that works:

1. Restate the problem in your own words and confirm. Thirty seconds that prevent solving the wrong problem.
2. Ask about constraints and edge cases: input size (decides whether O(n²) is acceptable), value ranges, negatives, duplicates, empty input, sorted or not, memory limits, unicode. Write down the ones that matter.
3. Work a small example by hand. This is where the pattern usually reveals itself, and it gives you test data for later.
4. State the brute force first, with its complexity. Never skip this — it proves you understand the problem and gives you a fallback if you run out of time.
5. Improve it out loud. "The brute force recomputes the sum of every window; I can slide instead and reuse work — that takes it from O(n·k) to O(n)."
6. Confirm the approach before coding. "Does that sound reasonable to you?" A good interviewer will save you from a dead end here.
7. Code cleanly. Real names, small helpers, handle edge cases you named. Talk while you type, but pause the narration for the tricky part rather than babbling.
8. Trace your code on the example, line by line, out loud. This catches most bugs and is the single most underused technique.
9. State final complexity in time and space, and say what you would improve with more time.

What do you do when you are completely stuck?

Do not go silent — silence is the only unrecoverable failure mode. Say what you are thinking: "I'm trying to find a way to avoid recomputing this; the O(n²) approach is clear, let me think about what structure would give me the previous answer in O(1)."

Then apply a checklist out loud: Would sorting help? Would a hash map remove a nested loop? Is there a monotonic property to binary search on? Can I solve it for n=1, n=2 and generalise? Is this secretly a graph? Would processing right-to-left be easier? Can I trade space for time?

And ask for a hint if you have been stuck for two or three minutes. Interviewers expect it; a candidate who takes a hint and runs with it scores far better than one who stalls for twenty minutes in pride.

How much does an optimal solution matter?

Less than you think. A working, clearly-explained, well-tested O(n²) solution usually beats a broken half-written O(n) one. The rubric typically covers problem solving, coding ability, communication, and testing — only one of those is "found the optimal algorithm". Get something correct on the board early, then optimise; a working solution is leverage, an empty screen is not.

How should you test your solution?

Before they ask. Walk through: the given example, an empty input, a single element, all-identical elements, the maximum size (does it overflow or time out?), negatives and zero, and whatever edge case your own logic introduces (an index at a boundary, an empty stack pop). Say "let me check the empty case — arr[0] would throw here, so I need a guard" and fix it yourself. Catching your own bug reads far better than an interviewer catching it.

What should you practise, and how?

Quality over quantity: 150 well-understood problems beat 600 skimmed ones. Practise by pattern, not randomly — do eight sliding-window problems in a row until the shape is automatic. Use a timer (25 minutes for a medium). After each problem, write two sentences on the insight, not the code; that is what transfers.

Always speak out loud, even when practising alone — the gap between "I can solve this" and "I can solve this while explaining it to a stranger who is judging me" is the entire difficulty of the interview. Do at least a few mock interviews with a real human before the real thing.

How do you handle a problem you have already seen?

Say so. "I've seen a version of this before, so I know the approach uses a monotonic stack — would you like me to solve it anyway or would you prefer a different problem?" Almost every interviewer will say carry on, and now your fast, clean solution reads as honesty rather than a suspiciously instant recall. Pretending you have not seen it and producing an optimal solution in ninety seconds with no derivation is the version that raises doubts.